一、基本二分法的描述
二分搜索（英语：binary search），也称折半搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
二、基本二分法的步骤与实现方法
- 二分法的前提：已排好序的数组A[n], 其中 A[0] <= A[1] <= ... <= A[n],以及一个待查找的值K。
- 步骤：
1. 令low = 0， high = n - 1，初始的查找区域为[low， high].
2. 取low和high的中间值mid = (low+high)/2。
3. 如果A[mid] = K，则返回mid, 如果不等，则重新确定查找区间。
4. 当low > high 时，则表示区间已经失效，如果还未找到，则表示数组中不包含K的值，返回-1。- 重新确定查找区间的规则：
1. 如果A[mid] < K, 则由数组的有序性可知T应该存在于[mid+1, high]之间。
2. 同理，如果A[mid] > K, 则T应该存在于[low, mid-1]区间。
- 代码如下：
template<class T>
int binary_search(vector<T> &A, T K)
{
int low = 0;
int high = A.size() - 1;
while( low < high )
{
int mid = (low + high)/2;
if( A[mid] < K )
low = mid + 1;
else if( A[mid] > k )
high = mid - 1;
else
return mid;
}
return -1; /*返回-1表示数组不存在K的值*/
}
三、二分法的变形算法
3.1 求数组中最大值
- 给定一个数组A，长度为n，其中A[0] < A[1] ... < A[i] > A[i+1] > ... > A[n-1]，求其中的最大值，返回其下标。
template<class T>
int binary_serach_peek(vector<T> &A)
{
int low = 0;
int high = A.size() - 1;
while( low < high )
{
int mid = low + (high - low)/2;
if( A[mid] > A[mid-1] && A[mid] > A[mid+1])
return mid;
else if( A[mid] > A[mid-1] && A[mid] < A[mid+1])
low = mid;
else
high = mid;
}
return -1;
}
