二分查找(Binary Search)

二分查找算法在程序设计中并不陌生,它可以在O(log(n))的时间复杂度内找到自己想要的值。

首先需要待查找序列有序,然后需要你想要寻找的值即可,本文给出三种二分查找的例子,即:

  1. 精确二分查找,如果找不到返回error
  2. 进行精确查找,如果找不到则返回第一个小于该数值的元素的位置
  3. 进行精确查找,如果找不到则返回第一个大于该数值的元素的位置

首先我们来看第一种(也是最简单的):

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”也是这个原因,请读者注意。

如有错误敬请指出,感谢阅读!

二分查找(Binary Search)

上一篇:笔趣阁小说爬虫


下一篇:Elaticsearch基础概念