二分查找

二分查找是一个比较简单的算法，用 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

有关心情