0x02 有序数组查找

Make it work, make it right, make it fast.

—Kent Beck

通常提到的数组是指计算机中的概念（而非数学中的数组），即一段连续的内存空间，用来存放相同类型的数据。 有的时候数组的概念与序列可以相互替代，这取决于上下文的语境，有的时候则不能。

有序数组查找问题（Sorted array searching problem）

输入：

由 \(n\) 个数字组成的有序数组 \(A=\left\langle a_1, a_2, \ldots, a_n\right\rangle\), 以及一个待查找的数字 \(k\).

输出：

如果 \(k\) 存在于数组 \(A\) 中，则返回任意满足条件元素的下标 \(i\)，否则返回 \(-1\).

顺序查找

顺序查找（Sequential search），也叫线性查找（Linear search），其基本思想是：

1. 从数组的第一个元素开始，依次与待查找的数字进行比较，相等则停止；

2. 如果最终所有元素都与待查找的数字不相等，则查找失败。

这体现了减而治之的思想：每次将问题规模缩小一个单位，时间复杂度：\(O(n)\)

小技巧

这种暴力解法（Brute-force）也叫做 穷举法（Exhaustive method），没有思路时不妨从穷举开始。 在实际应用中，通常不会使用这种方法，而是使用更加高效的算法。 顺序查找元素对于随机排列的数组也奏效，但这从侧面反映出我们在设计算法时，没有充分利用初始数据的特征：有序性。

同样是减而治之，如何更快地减小问题规模？这启发我们设计更加高效的算法。

二分查找算法

狭义的 二分查找（Binary search） 也叫折半查找（Half-interval search），其基本思想是：

1. 从数组的中间元素开始，如果中间元素正好是要查找的数字，则查找过程结束；否则，

2. 如果中间元素大于要查找的数字，则在数组的前半部分继续查找，否则在数组的后半部分继续查找；

3. 重复上述过程，直到找到要查找的数字，或者数组中没有要查找的数字。

这体现了减而治之的思想：但每次将问题规模缩小一半，时间复杂度：\(O(\log n)\)

任意元素

在数组 array 区间 [left, right] 中查找数字 k，如果找到则返回其下标，否则返回 -1:

迭代版

int binary_search(vector<int> &array, int left, int right, int k) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] < k) left = mid + 1;
        else if (array[mid] > k) right = mid - 1;
        else return mid;
    }
    return -1;
}

递归版

int binary_search(vector<int> &array, int left, int right, int k) {
    if (left > right) return -1;

    int mid = left + (right - left) / 2;
    if (array[mid] < k) return binary_search(array, mid+1, right, k);
    else if (array[mid] > k) return binary_search(array, left, mid-1, k);
    else return mid;
}

Wikipedia LeetCode 704

值得注意的是， if-else 语句的设计，在常数意义上有着微妙的影响，我们会在后面的小节介绍。

参见

自行了解 std::binary_search 的用法。

重复元素

但是在实际应用中，对于出现多个满足条件元素的情况，通常对返回结果有着更加准确的要求。 此时二分查找算法需要关注的重点是 正确地处理边界问题，下面提供一份比较容易记忆的模板（规律很强）：

首次出现

目标元素可能在数组中出现多次，但是我们只关心其首次出现的位置：

// Eg. 1 2 3 3 3 4 5 (k = 3)
//         ^
int binary_search_first(vector<int> &array, int left, int right, int k) {
    int l = left, r = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] < k) left = mid + 1;
        else right = mid - 1;
    }
    if (left <= r && array[left] == k) return left;
    return -1;
}

💡 原理解释

• 每次找到匹配元素时，更新右边界 right 至不含当前匹配位置。（找最左，频删右）

• 注意由于这是一种比较傲娇的边界更新策略，如果至少存在一个匹配元素，

  • 搜索的右边界 right 最终会跑到首次出现位置的左边，此后无论如何找不到匹配元素；

  • 而 left 经过不断更新，最终将跑到 right 的右邻侧（即 right+1），恰好是首次出现位置。

• 由于还可能存在找不到的情况，我们还需要进行额外判断，最终逻辑是：

  • 若 left 越过右边界，说明数组中的所有元素都小于目标元素，返回 -1；

  • 若 left 位置的元素不等于目标元素，说明数组中所有元素都大于目标元素，返回 -1；

  • 否则返回 left 位置的元素下标，即为目标元素的首次出现位置。

找最后出现位置（即最右匹配元素位置）的情况与上述情况类似。

最后出现

目标元素可能在数组中出现多次，但是我们只关心其最后出现的位置：

// Eg. 1 2 3 3 3 4 5 (k = 3)
//             ^
int binary_search_last(vector<int> &array, int left, int right, int k) {
    int l = left, r = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] <= k) left = mid + 1;
        else right = mid - 1;
    }
    if (right >= l && array[right] == k) return right;
    return -1;
}

Wikipedia LeetCode 34 LintCode 14 LintCode 458 AcWing 789

参见

自行了解 std::lower_bound 和 std::upper_bound 的用法。

备注

这种实现当然也能够处理查找任意满足条件元素的情况，但：

• 在最好情况下，比原方法要坏，因为即使找到了，也要在最后确认；

• 在最坏情况下，比原方法要好，因为减少了比较操作的次数。

这些差异都是常数意义的，不会影响算法的渐近复杂度，依旧为 \(O(\log n)\).

寻找插入位置

有序数组插入问题（Sorted array insertion problem）

输入：

由 \(n\) 个数字组成的有序数组 \(A=\left\langle a_1, a_2, \ldots, a_n\right\rangle\), 以及一个待插入的数字 \(k\).

输出：

若要将 \(k\) 插入到数组 \(A\) 中，返回首个满足条件的插入位置，使得 \(A\) 仍然保持有序。

如果你已经阅读了 重复元素 小节的内容，以下代码并不难理解：

int search_insertion(vector<int> &array, int left, int right, int k) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] < k) left = mid + 1;
        else right = mid - 1;
    }
    return left;
}

LeetCode 35 LintCode 60

💡 原理解释

• 若待插入元素已经存在，问题转化为寻找重复元素首次出现位置；

• 若待插入元素不存在，问题转化为寻找第一个大于待插入元素的元素位置：

  • 若数组中所有元素均小于待插入元素，返回末尾元素后方的位置；

  • 若数组中所有元素均大于待插入元素，返回首个元素的位置;

• 有趣的是，在二分查找更新边界的过程中，以上情况都能够用 left 来表示相应位置。

❓ 折半查找策略能降低插入排序的复杂度吗

结论是：不能。折半查找策略能够帮助我们在 \(O(\log n)\) 次数的比较中找到插入位置，但是数组的插入操作本身仍然需要 \(O(n)\) 的时间复杂度。 你可能回想起我们前面曾说过，影响 选择排序 时间复杂度的关键是比较次数，而影响插入排序时间复杂度的关键是插入操作本身。

寻找最优二分策略

要将一个数组一分为二，有很多种不同的方法，区间内的任何一个元素都可以作为划分的轴点。 这自然引发我们去思考，我们采用的折半查找策略，在广义的二分查找中是否是通用的最优策略呢？ 实际上，这与我们的程序结构设计脱离不了干系。

备注

后续小节讨论的是常数意义优化，不感兴趣的读者可直接跳过。

斐波那契查找算法

实际上，我们在处理重复元素查找时，已经通过将 array[mid] == k 的情况合并入 if-else 分支， 使得无论如何 if-else 比较次数都恒为 1, 达到了理想的平衡状态。

不难发现，我们每次通过比较选定位置的元素与目标元素的大小关系，都会将搜索区间缩小。 二分查找采取了一种比较折中的策略，能够稳定地每次将问题规模缩小一半，因此其时间复杂度为 \(O(\log n)\). 但不难发现，不论是递归还是迭代实现，在确定下一次搜索区间前，我们都需要进行一至多次的比较：

• 具体而言，即 if-elseif 语法自身也会存在一定的时间开销；

• 理想情况下，我们倾向于将出现概率最高的情况放在 if 语句中；

比较操作的不平衡问题

这就导致对于不同的目标元素，最终的比较次数其实并不均匀。考虑以下数列：

\[ [1, 2, 3, 4, 5, 6, 7, 8] \]

假如按照 二分查找算法 中给出的算法实现，在搜索目标元素 \(1\) 时， 每次都需要执行两次比较，才能开始缩短区间。 而搜索 \(8\) 时，当执行一次比较后，就可以缩短区间了。

黄金分割比

借助平均时间复杂度理论分析，可证明出最优做法（我们这里不给出推导）：

假定我们每次都能够将搜索区间缩小到原来的 \(\frac{1}{\phi}\)，其中 \(\phi\) 是黄金分割比，即：

\[ \phi = \frac{1 + \sqrt{5}}{2} \approx 1.618 \]

则能够保证最坏情况下的比较次数为 \(O(\log n)\) 且其常数因子最小。

struct Fib {
  int f, g; 
  Fib(int n) { f = 1; g = 0; while (g < n) next(); }
  int get() { return g; }
  int next() { g += f; f = g - f; return g; }
  int prev() { f = g - f; g -= f; return g; }
};

int fibonacci_search(vector<int> &array, int left, int right, int k) {
    Fib fib(right - left);
    while (left <= right) {
        while ((right - left) < fib.get()) { fib.prev(); }
        int pos = left + fib.get();
        if (array[pos] < k) left = pos + 1;
        else if (array[pos] > k) right = pos - 1;
        else return pos;
    }
    return -1;
}

Wikipedia LeetCode 704

插值查找算法

插值查找算法的基本思想是：在有序数组中查找特定元素时，先计算出该元素应该在数组中的大致位置，然后将查找区间缩小到该位置附近，不断通过比较查找到该元素。

等于对数组中的分布性质进行了假设，服从均匀且独立的随机分布，大致按照线性趋势增长：

\[ \frac{\text{pos} - \text{left}} {\text{right} - \text{left}} = \frac{\text{target} - \text{array[left]}}{\text{array[right]} - \text{array[left]}} \]

因此可以变形得出，其选取大致位置的策略为：

\[ \text{pos} = \text{left} + \left( \text{right} - \text{left} \right) \times \frac{\text{target} - \text{array[left]}}{\text{array[right]} - \text{array[left]}} \]

int interpolation_search(vector<int> &array, int left, int right, int k) {
    while (left < right) {
        int pos = left + (right - left) * (k - array[left]) \
                      // -----------------------------------
                        / (array[right] - array[left]);
        if (array[pos] < k) left = pos + 1;
        else if (array[pos] > k) right = pos - 1;
        else return pos;
    }
    return array[left] == k ? left : -1;
}

该算法的时间复杂度为 \(O(\log n)\)，可以在大多数情况下达到很好的查找效率。 但是，当数组中元素分布不均匀时，可能会导致效率下降。因此，该算法通常适用于元素分布比较均匀的有序数组中的查找。

Wikipedia LeetCode 704

时间复杂度分析

每经过一次查找，问题规模由 \(n\) 变为 \(\sqrt{n}\) （证明见[7]），因此时间复杂度为 \(O(\log \log n)\).

估算方式：可借助二进制字宽来理解。对于规模为 \(n\) 的问题，其二进制表示的位宽为 \(\log n\), 每次插值查找后，问题规模变为 \(\sqrt{n}\), 从二进制角度来看，即其位数变为 \(\frac{1}{2} \log n\)， 经过对数次插值，最终问题位数变为 \(1\)，时间复杂度为 \(O(\log \log n)\). 在问题规模不大时， \(O(\log n)\) 与 \(O(\log \log n)\) 差异并不显著。

值得注意的是，在常数意义上，插值查找的效率并不一定比二分查找高， 因为插值查找需要进行乘法、除法运算，而二分查找只需要进行移位运算。

重要

一些算法通常也会假设数据服从特定的分布，例如高斯分布等，从而设计出更加高效的算法。 缺点在于，一旦数据分布不符合假设，算法的效率就会大幅下降，因此要 对症下药 。 我们将来会接触到采用类似思想的排序算法，以及统计机器学习算法等等。