二分查找(binary search)又称二分查找。其查找过程是，先确定待查记录所在范围，然后逐步缩小范围，直至找到该记录或者当查找区间缩小到0也没有找到关键字等于给定值的记录为止。
（1）代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//binarySearch.h #include <vector> using namespace std; int binarySearch(vector<int> &vec, int key) { //初始化两个下标分别指向数组的头部和尾部 int low = 0; int high = vec.size()-1; //如果low小于等于high，则一直循环下去 while(low <= high){ //初始化数组中间数的下标为mid int mid = (low+high)/2; //找到，则返回mid下标 if (vec[mid] == key) return mid; //若中间值大于待查找数，则继续查找左半部分 else if(vec[mid] > key) high = mid -1; //否则，中间值小于带查找数，则继续查找右半部分 else low = mid + 1; } //未找到，返回-1 return -1; } |
二分查找就是不断将key与数组中间的值比较，若没有找到就继续将数组折半查找…
（2）二分查找只能对顺序存储结构的有序表进行，时间复杂度为O(logn)。
（3）示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
using namespace std; int main() { vector<int> vec = {3, 4, 32, 199, 1051, 2119}; cout << "Try to find the key of 32..." << endl; int ret = binarySearch(vec, 32); if (ret == -1) cout << endl << "Can not find the key of 32." << endl; else cout << endl << "Found it at the index of: " << ret << endl; return 0; } |
输出：
|
1 2 3 |
Try to find the key of 32... Found it at the index of: 2 |