二分查找

ゞ浴缸里的玫瑰 2021-12-13 03:57 162阅读 0赞

# 二分查找 #

二分查找是一个比较简单的算法，用 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 的位置，但由于取不到这个位置上的值，所以不会造成重复取值。