基礎算法之二分查找

二分查找

利用分治法，逐漸蘇小查找範圍，适用于有序數組。

時間複雜度是O(log2N).

PS:二分查找算法的判定過程實際上可以借助一棵平衡二叉樹來描述，中間位置的關鍵字可以看成二叉樹的根節點。

C++代碼如下：

1 #include <iostream>
 2 using namespace std;
 3 template<class DataType>  int  binSearch(DataType key[],int n,DataType k)
 4 {
 5     int low=0,high=n-1;
 6     int mid;
 7     while(low<=high)
 8     {
 9         mid=(low+high)/2;
10         if(k == key[mid])
11         {
12             return mid;
13         }
14         else if(k>key[mid])
15         {
16             low=mid+1;
17         }
18         else
19         {
20             high=mid-1;
21         }
22     }
23 
24     return NULL;
25 }
26 
27 int main()
28 {
29     int data[] = {12,23,24,34,45,67,78,89,99};
30     int key;
31     cout<<"請輸入要查找的數字： ";
32     cin>>key;
33     cout<<endl;
34     int result = binSearch(data,10,key);
35     cout<<"您要查找的數字是： "<<key<<"，它的位置是： "<<result+1<<endl;
36     return 0;
37 }      

View Code

轉載于:https://www.cnblogs.com/yueyanglou/p/4515815.html