二分查找算法在程序设计中并不陌生,它可以在O(log(n))的时间复杂度内找到自己想要的值。
首先需要待查找序列有序,然后需要你想要寻找的值即可,本文给出三种二分查找的例子,即:
- 精确二分查找,如果找不到返回error
- 进行精确查找,如果找不到则返回第一个小于该数值的元素的位置
- 进行精确查找,如果找不到则返回第一个大于该数值的元素的位置
首先我们来看第一种(也是最简单的):
int binarySearch(int *arr, int n, int value) {
int l, r, mid;
l = 0;
r = n - 1;
mid = 0;
while (l <= r) {
mid = (l + r) / 2;
if (arr[mid] < value) {
l = mid + 1;
}
else if (arr[mid] > value) {
r = mid - 1;
}
else {
return (mid);
}
}
return -1;//error
}
简单易读。没找到就一直缩小区间,直到找到或者二分辅助变量l(左边界)与r(右边界)不符合要求,此时返回error。
下面来看第二种情况的代码:
int binarySearch(int *arr, int n, int value) {
int l, r, mid;
l = 0;
r = n - 1;
mid = 0;
while (l <= r) {
mid = (l + r) / 2;
if (arr[mid] < value) {
l = mid + 1;
}
else if (arr[mid] > value) {
r = mid - 1;
}
else {
break;
}
}
if (arr[mid] != value && arr[mid] > x) {
mid--;
}
return mid;
}
此时,无法找到第一个小于value的数(比如数列“1, 2, 3, 4, 5”中查找“0”是无法找到第一个小于它的数的),返回(左边界 - 1)*,此时需要程序进行特殊处理。
最后我们来看一下最后一种情况的代码:
int binarySearch(int *arr, int n, int value) {
int l, r, mid;
l = 0;
r = n - 1;
mid = 0;
while (l <= r) {
mid = (l + r) / 2;
if (arr[mid] < value) {
l = mid + 1;
}
else if (arr[mid] > value) {
r = mid - 1;
}
else {
break;
}
}
if (arr[mid] != value && arr[mid] < x) {
mid++;
}
return mid;
}
此时,无法找到第一个大于value的数(比如数列“1, 2, 3, 4, 5”中查找“6”是无法找到第一个大于它的数的),返回(右边界 + 1)*,此时需要程序进行特殊处理。
*解释一下所谓的“左边界”与“右边界”,个人的编程习惯中在使用数组等结构时会使用0~n-1这n个位置,区别于使用1-n这n个位置,即遍历操作为:
for (int i = 0; i < n; i++) { //do something with arr[i] }
上问代码中对于“l”、“r”的初始值为“0”、“n - 1”也是这个原因,请读者注意。
如有错误敬请指出,感谢阅读!