二分查找算法

二分查找（Binary Search) 又称折半查找，它是一种效率比较高的查找方法。但是，这种查找方法的前提是： “已经排序好的线性表”。

时间复杂度O(lgn)。

 1 #include <iostream>
 2 using namespace std; 
 3 int BinSearch(const int* Array,int start,int end,int key)
 4 {
 5     int left,right;
 6     int mid;
 7     left=start;
 8     right=end;
 9      
10     while(left<=right)
11     {
12         mid = (left + right)/2;
13  
14         if(key < Array[mid])
15         {
16             right = mid - 1;
17         }
18         else if(key > Array[mid])
19         {
20             left = mid + 1;
21         }
22         else
23             return mid;
24     }
25     return -1;
26 }
27  
28 int main(int argc,char* argv[])
29 {
30     int a[11] ={ 1,3,5,6,10,14,16,20,21,23,28};
31  
32     int _findInt =BinSearch( a,0,(sizeof a)/(sizeof a[0]),23);//(sizeof a)/(sizeof a[0])数组的长度 
33     if(_findInt == -1)
34     {
35         cout<<"-1"<<endl;
36     }
37     else
38     {
39         cout<<"at  "<<_findInt<<endl;
40     }
41      
42      return 0;
43 }