二分查找

数学基础 2019-07-14 2684 字 419 浏览 点赞

二分查找是一个比较简单的算法,用 C++ 语言实现如下:

template <typename T>
int binary_search(
        const T& key,  // 搜索元素 key
        vector<int>::const_iterator data,  // 数组起始位置
        int N)  // 元素个数
{
    // 左闭右闭
    int low = 0;
    int high = N - 1;

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (key < *(data + mid))
            high = mid - 1;
        else if (key > *(data + mid))
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

用法:
// vector<int> arr = {1, 2, 3, 4, 5, 65};
// cout << binary_search(5, arr.cbegin(), 6) << endl;
// cout << binary_search(1, arr.cbegin(), 6) << endl;
// cout << binary_search(4, arr.cbegin(), 6) << endl;


相信实现原理大家都知道,无非是:将搜索元素 key 与 mid 指向的元素做比较,通过挪动首尾指针,逐步收拢搜索范围,最后找出 key 在数组中的位置。

然而这里有个问题是初学者想不明白的。由于网上二分搜索的版本太多,一一看过后,什么时候用 low < high,什么时候用 low <= high;什么时候是high = mid,什么时候又是 high = mid - 1 …… 总之,全然迷糊了。

一个运算符的用错会导致二分搜索出错,所以在这里我想说的是:如何理解二分搜索的细节处理?


现有数组 vector<int> v = {1, 2, 3, 4, 5, 6, 7}。为写代码方便,我们需要设置 low、high 两个指针,一个指向数组里的头元素,一个指向数组里的尾元素,就像下面那样。

| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
  |           |           |
 low         mid         high

同时根据二分法原理,还需要一个中间指针 mid,指向 low 与 high 中间的元素。

一、mid 应该如何计算?

  • 首先,我们可以确定的是,元素的索引范围是 [low, high](左闭右闭,这个很关键)。
  • 其次,假设元素个数为奇数,一定会有从 low 到 mid 和从 mid 到 high 的距离相等。那么:mid + 1 - low = high + 1 - mid ==> mid = (low + high) / 2

二、退出循环的条件是什么?

二分搜索中,如果第一次没找到搜索元素 key,进行第二次、第三次……搜索,所以需要一个循环体。既然有循环,我们就得知道循环的退出条件。

  • 当 low = 1, high = 3,且未找到搜索元素 key,可以退出循环吗?当然不能,因为此刻索引的取值区间为 [1, 3],在这个区间里还能取到 index = 1, 2, 3,还得继续二分比较。
  • 当 low = 2, high = 2 且未找到 key,此时区间为 [2, 2],区间里还能取到 index = 2,因此还是不能退出。只有当区间取值为空时,才可以退出循环。

[low, high] 左闭右闭前提下,只有当 low > high,循环才可以退出。所以循环条件是:low <= high。

三、应该 high = mid 还是 high = mid - 1?

现在我们将问题场景化。假设我们要在上述数组 v 中寻找数字 2 的位置,那么:

  • 第一轮比较得出 v[mid] > 2,也就是 high 指向的元素太大,需要左移。但由于 mid 指向的数字 4 已经参与过比较,且整个计算过程中我们使用的是左闭右闭 [low, high] 区间,倘若 high 指向了 mid 指向的值(此次是数字 4),区间变成了[low, 4],可能出现数字 4 被重复使用。
  • 为进一步优化,应该是 high = mid - 1。

同理,low 应该如何移动呢?既然“左闭”,为不重复取值,所以 low = mid + 1。


二分搜索的另一种版本是,对索引取值范围不采用左闭右闭,而是左闭右开。如下边这样:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 |   
  |           |               |
 low         mid             high

在代码中的体现:

// 左闭右开
int low = 0;
int high = N;

根据前边的推导方式,我们可以得出以下不同:

  • mid 取值:(high - 1 + low) / 2
  • 退出循环的条件:low >= high。因为是左闭右开,所以当 low = high 时,[low, high) 这个区间就取不到值了。用数字代入即懂,比如 low = high = 3,区间为 [2, 2),取值为空。
  • high 指针左移:high = mid。作为“右开”,尽管 high 指针移到了 mid 的位置,但由于取不到这个位置上的值,所以不会造成重复取值。


本文由 Guan 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论