二分查找

二分查找的基本思想:

是将n个元素分成大致相等的两部分，取arr[n/2]与target做比较，如果target=arr[n/2],则找到target,算法中止;如果target<arr[n/2],则只要在数组arr的左半部分继续搜索target,如果target>arr[n/2],则只要在数组arr的右半部搜索target.
优点：
查找速度快
缺点：
待查表为有序表
代码实现：

 1 #include <iostream>
 2 using namespace std;
 3 //二分查找法查找有序数组arr中的target元素
 4 //如果找到target元素，返回相应的索引index
 5 template<typename T>
 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 }

posted on 2018-12-11 23:42 Tom-shushu 阅读(...) 评论(...) 编辑收藏

二分查找

二分查找

相关文章