二分查找
2019年6月11日 星期二, 发表于 深圳
如果你对本文有任何的建议或者疑问, 可以在 这里给我提 Issues, 谢谢! :)
二分查找常用于有序序列中的查找，提供O(logN)的时间复杂度，其基本原理比较简单，但是正确的实现并不太容易：
1. binary_search
c++实现代码：
//返回索引，查不到返回-1;
int binary_search(int arr[], int arrlen, int value)
{
int low = 0, high = arrlen - 1;
while (low <= high )
{
int middle = (low + high) / 2;
if ( value == arr[middle] ) return middle;
else if (value > arr[middle]) low = middle + 1;
else high = middle - 1;
}
return -1;
}
int main(int argc, char** argv)
{
int arr[] = { 0,1,2,3 };
cout << binary_search(arr, sizeof(arr)/sizeof(int), 7) << endl;
}
这里容易出错的就是控制结束的条件，我个人是这么理解的；
- 小于控制是必须的，因为这个时候代表数列还没有完全遍历完成，容易理解；
- 等于的情况，可以设想序列只有一个元素，此时也是应该进入循环的；
当然，真正使用的时候，可以多参考stl的实现：https://zh.cppreference.com/w/cpp/algorithm/binary_search；
stl中的二分查找在c++11中只支持升序，这个需要注意一下；
2. lower_bound & upper_bound
- lower_bound返回有序数组中的下限（第一个大于等于findKey的元素）；
- upper_bound返回有序数组中的上限（第一个大于findKey的元素）；
int lower_bound(int arr[], int arrlen, int value)
{
int low = 0, high = arrlen - 1;
while (low <= high)
{
int middle = (low + high) / 2;
if (value == arr[middle]) high = middle - 1; //向左边扩展边界
else if (value > arr[middle]) low = middle + 1;
else high = middle - 1;
}
return low;
}
int upper_bound(int arr[], int arrlen, int value)
{
int low = 0, high = arrlen - 1;
while (low <= high)
{
int middle = (low + high) / 2;
if (value == arr[middle]) low = middle + 1; //向右扩展边界
else if (value > arr[middle]) low = middle + 1;
else high = middle - 1;
}
return low;
}
这个地方和上面二分查找区别在 value == arr[middle]的处理情况，lower_bound如果相等，应该向左边扩展边界，而upper_bound向右扩充边界