(searching-in-sorted-array)=
# 0x02 有序数组查找

```{epigraph}
Make it work, make it right, make it fast.

-- Kent Beck
```

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

```{admonition} 有序数组查找问题（Sorted array searching problem）
:class: note
:name: array-search-problem
**输入：** 
: 由 $n$ 个数字组成的有序数组 $A=\left\langle a_1, a_2, \ldots, a_n\right\rangle$, 以及一个待查找的数字 $k$.

**输出：** 
: 如果 $k$ 存在于数组 $A$ 中，则返回任意满足条件元素的下标 $i$，否则返回 $-1$.
```

(sequantial-search)=
## 顺序查找

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

1. 从数组的第一个元素开始，依次与待查找的数字进行比较，相等则停止；
2. 如果最终所有元素都与待查找的数字不相等，则查找失败。

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

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

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

(binary-search)=
## 二分查找算法

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

1. 从数组的中间元素开始，如果中间元素正好是要查找的数字，则查找过程结束；否则，
2. 如果中间元素大于要查找的数字，则在数组的前半部分继续查找，否则在数组的后半部分继续查找；
3. 重复上述过程，直到找到要查找的数字，或者数组中没有要查找的数字。

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

(binary-search-any)=
### 任意元素

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

`````{tab-set}

````{tab-item} 迭代版
```{code-block} cpp
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;
}
```
````

````{tab-item} 递归版
```{code-block} cpp
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;
}
```
````

`````

{bdg-link-primary-line}`Wikipedia <https://en.wikipedia.org/wiki/Binary_search_algorithm>`
{bdg-link-primary-line}`LeetCode 704 <https://leetcode.com/problems/binary-search/>`

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


```{seealso}
自行了解 `std::binary_search` 的用法。
```

(binary-search-duplicate-elements)=
### 重复元素

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

`````{tab-set}

````{tab-item} 首次出现

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

```{code-block} cpp
// 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;
}
```

```{dropdown} 💡 原理解释
:animate: fade-in-slide-down

- **每次找到匹配元素时，更新右边界 `right` 至不含当前匹配位置**。（找最左，频删右）
- 注意由于这是一种比较傲娇的边界更新策略，如果至少存在一个匹配元素，
  - 搜索的右边界 `right` 最终会跑到首次出现位置的左边，此后无论如何找不到匹配元素；
  - 而 `left` 经过不断更新，最终将跑到 `right` 的右邻侧（即 `right+1`），恰好是首次出现位置。
- 由于还可能存在找不到的情况，我们还需要进行额外判断，最终逻辑是：
  - 若 `left` 越过右边界，说明数组中的所有元素都小于目标元素，返回 `-1`；
  - 若 `left` 位置的元素不等于目标元素，说明数组中所有元素都大于目标元素，返回 `-1`；
  - 否则返回 `left` 位置的元素下标，即为目标元素的首次出现位置。

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

```

````

````{tab-item} 最后出现

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

```{code-block} cpp
// 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;
}
```
````

`````

{bdg-link-primary-line}`Wikipedia <https://en.wikipedia.org/wiki/Binary_search_algorithm#Duplicate_elements>`
{bdg-link-primary-line}`LeetCode 34 <https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/>`
{bdg-link-primary-line}`LintCode 14 <https://www.lintcode.com/problem/first-position-of-target>`
{bdg-link-primary-line}`LintCode 458 <https://www.lintcode.com/problem/last-position-of-target>`
{bdg-link-primary-line}`AcWing 789 <https://www.acwing.com/problem/content/791/>`

```{seealso}
自行了解 `std::lower_bound` 和 `std::upper_bound` 的用法。
```

```{note}
这种实现当然也能够处理查找任意满足条件元素的情况，但：
- 在最好情况下，比原方法要坏，因为即使找到了，也要在最后确认；
- 在最坏情况下，比原方法要好，因为减少了比较操作的次数。

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

(insertion-place-search)=
### 寻找插入位置

```{admonition} 有序数组插入问题（Sorted array insertion problem）
:class: note
:name: insertion-place-search-problem
**输入：** 
: 由 $n$ 个数字组成的有序数组 $A=\left\langle a_1, a_2, \ldots, a_n\right\rangle$, 以及一个待插入的数字 $k$.

**输出：** 
: 若要将 $k$ 插入到数组 $A$ 中，返回首个满足条件的插入位置，使得 $A$ 仍然保持有序。
```

如果你已经阅读了 {ref}`binary-search-duplicate-elements` 小节的内容，以下代码并不难理解：

```{code-block} cpp
:emphasize-lines: 7

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;
}
```

{bdg-link-primary-line}`LeetCode 35 <https://leetcode.com/problems/search-insert-position/>`
{bdg-link-primary-line}`LintCode 60 <https://www.lintcode.com/problem/search-insert-position>`

```{dropdown} 💡 原理解释
:animate: fade-in-slide-down

- 若待插入元素已经存在，问题转化为寻找重复元素首次出现位置；
- 若待插入元素不存在，问题转化为寻找第一个大于待插入元素的元素位置：
  - 若数组中所有元素均小于待插入元素，返回末尾元素后方的位置；
  - 若数组中所有元素均大于待插入元素，返回首个元素的位置;
- 有趣的是，在二分查找更新边界的过程中，以上情况都能够用 `left` 来表示相应位置。
```

```{dropdown} ❓ 折半查找策略能降低插入排序的复杂度吗
:animate: fade-in-slide-down

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

### 寻找最优二分策略

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

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

(fibonacci-search)=
## 斐波那契查找算法

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

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

- 具体而言，即 `if-elseif` 语法自身也会存在一定的时间开销；
- 理想情况下，我们倾向于将出现概率最高的情况放在 `if` 语句中；

### 比较操作的不平衡问题

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

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

假如按照 {ref}`binary-search` 中给出的算法实现，在搜索目标元素 $1$ 时，
每次都需要执行两次比较，才能开始缩短区间。
而搜索 $8$ 时，当执行一次比较后，就可以缩短区间了。

### 黄金分割比

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

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

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

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

```{code-block} cpp
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;
}
```

{bdg-link-primary-line}`Wikipedia <https://en.wikipedia.org/wiki/fibonacci_search_technique>`
{bdg-link-primary-line}`LeetCode 704 <https://leetcode.com/problems/binary-search/>`

(interpolation_search)=
## 插值查找算法

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

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

$$
\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]}}
$$

```{code-block} cpp
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)$，可以在大多数情况下达到很好的查找效率。
但是，当数组中元素分布不均匀时，可能会导致效率下降。因此，该算法通常适用于元素分布比较均匀的有序数组中的查找。

{bdg-link-primary-line}`Wikipedia <https://en.wikipedia.org/wiki/interpolation_search>`
{bdg-link-primary-line}`LeetCode 704 <https://leetcode.com/problems/binary-search/>`

```{admonition} 时间复杂度分析
:class: note
每经过一次查找，问题规模由 $n$ 变为 $\sqrt{n}$ （证明见{cite:p}`yao87`），因此时间复杂度为 $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)$ 差异并不显著。

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

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