二分查找的基本思想:

是将n个元素分成大致相等的两部分，取arr[n/2]与target做比较，如果target=arr[n/2],则找到target,算法中止;如果target<arr[n/2],则只要在数组arr的左半部分继续搜索target,如果target>arr[n/2],则只要在数组arr的右半部搜索target.

优点：

查找速度快

缺点：

待查表为有序表

代码实现：

1 #include 
       
         2 using namespace std; 3 //二分查找法查找有序数组arr中的target元素 4 //如果找到target元素，返回相应的索引index 5 template
        
          6 int binarySearch(T arr[],int n ,T target){ 7     //arr[l......r] 8     int l = 0 ,r = n-1; 9     while( l <= r ){10         //int mid = (l+r)/2;11         int mid = l+(r-l)/2;12         if (arr[mid] == target)13             return mid;            14             if(target < arr[mid])15             r = mid - 1;16             else 17             l = mid +1;18             }19             return -1;    20 } 21 int main() {22     return 0;23 }