二分查找(Binary Search)是一种常见的查找算法，可以以\(O(\log n)\)的时间复杂度在排好顺序（本文假定为升序）的数组中查找特定的数据。查找的方式与我们小时候玩过的猜数游戏极其相似，基本原理是将需要查找的区间从中间分为两个子区间，并判断中间值与要查找的值的大小，以确定要查找的值位于左右哪个区间，再重复相同步骤直到找到值或发现该值不存在。
具体的代码实现如下：
#include <iostream>
using namespace std;
int binary_search_lower(int *data, int n, int value)
{
int l = 0;
int r = n - 1;
int mid = (l + r) >> 1;
while(l < r)
{
if(data[mid] >= value)
r = mid;
else
l = mid + 1;
mid = (l + r) >> 1;
}
if(data[l] == value)
return l;
return -1;
}
int binary_search_upper(int *data, int n, int value)
{
int l = 0;
int r = n - 1;
int mid = (l + r + 1) >> 1;
while(l < r)
{
if(data[mid] <= value)
l = mid;
else
r = mid - 1;
mid = (l + r + 1) >> 1;
}
if(data[l] == value)
return l;
return -1;
}
int main()
{
int a[] = {1, 2, 3, 4, 4, 4, 5, 6, 7, 8};
cout << "L: " << binary_search_lower(a, sizeof(a) / sizeof(int), 4) << endl;
cout << "U: " << binary_search_upper(a, sizeof(a) / sizeof(int), 4) << endl;
return 0;
}注意，在上面的代码中，我们使用>>1来取中间值，这样可以保证我们的mid取值永远是向下取整的，而如果使用/2则是向零取整。
二分查找共有两种查找方式，在上面的代码示例中均有给出，lower表示当有相同值时返回最靠低位的值的位置，即从低向高查找，而upper正好相反。上面代码给出的示例数据也可以反映出这一特点。
发表回复