Board logo

標題: 二分搜尋法 [打印本頁]
作者: tonyh    時間: 2018-6-20 14:11     標題: 二分搜尋法

本帖最後由 tonyh 於 2018-6-20 16:18 編輯

說明
如果搜尋的數列已經有排序，應該儘量利用它們已排序的特性，以減少搜尋比對的次數，這是搜尋的基本原則，二分搜尋法（Binary Search）是這個基本原則的代表。

解法
在二分搜尋法中，從數列的中間開始搜尋，如果這個數小於我們所搜尋的數，由於數列已排序，則該數左邊的數一定都小於要搜尋的對象，所以無需浪費時間在左邊的數；如果搜尋的數大於所搜尋的對象，則右邊的數無需再搜尋，直接搜尋左邊的數。
所以二分搜尋法，就是將數列不斷的分為兩個部份，每次從分割的部份中取中間數比對，反覆這個步驟直到比對成功。

範例
例如要搜尋92於以下的數列，首先中間數索引為(0+9)/2=4（索引由0開始）：
[3 24 57 57 67 68 83 90 92 95]

由於67小於92，所以轉搜尋右邊的數列：
3 24 57 57 67 [68 83 90 92 95]

由於90小於92，再搜尋右邊的數列，這次就找到所要的數了：
3 24 57 57 67 68 83 90 [92 95]

優點
搜尋效率較佳

缺點
資料必須事先排序

範例練習

int data[9]= {5, 9, 13, 15, 17, 19, 25, 30, 45};  // 已排序資料

[attach]4247[/attach]

[attach]4248[/attach]
  1. #include<iostream>
  2. #include<cstdlib>
  3. using namespace std;
  4. int main()
  5. {
  6.     int target;
  7.     int data[9]= {5, 9, 13, 15, 17, 19, 25, 30, 45};  // 已排序資料
  8.     int high=sizeof(data)/sizeof(int)-1;
  9.     int low=0;
  10.     int middle=0;
  11.     int n=0;
  12.    
  13.     cout<<"請輸入要找尋的資料：";
  14.     cin>>target;
  15.     cout<<endl;
  16.     while(low<=high)
  17.     {
  18.         n++;
  19.         middle=(high+low)/2;
  20.         cout<<"尋找區間:"<<low<<"("<<data[low]<<").."<<high<<"("<<data[high]<<"),中間:"<<middle<<"("<<data[middle]<<")"<<endl;
  21.         if(target>data[middle])
  22.             low=middle+1;
  23.         else if(target<data[middle])
  24.             high=middle-1;
  25.         else
  26.             break;
  27.     }
  28.         
  29.     cout<<endl<<"經過"<<n<<"次的尋找"<<endl;
  30.     if(target==data[middle])
  31.         cout<<"您要找的資料在陣列中的第"<<middle<<"個位置";
  32.     else
  33.         cout<<target<<"不在陣列中";
  34.     cout<<endl<<endl;   
  35.     system("pause");
  36.     return 0;
  37. }
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2