Chapter 6: 搜索

增删改我们聊的挺多了，但是查该如何去执行呢？

搜索算法

线性搜索 (Linear Search)

最简单的查找方式就是线性搜索 (Linear Search) 了。线性搜索的方法非常简单，例如在数组里，我们就从头到尾按照index把整个数组扫一遍。找到就停下。

1
2
3
4
5
6

int linearSearch(int A[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (A[i] == x) return i;
    }
    return -1; // 没找到
}

这样的搜索方式荣获$O(n)$。好处是我们不需要对进行搜索的对象进行任何预处理。

1
2
3
4
5
6

int linearSearchSentinel(int A[], int n, int x) {
    A[n] = x; // 哨兵（需保证数组有额外空间）
    int i = 0;
    while (A[i] != x) i++;
    return i < n ? i : -1;
}

二分搜索 (Binary Search)

那么你问到什么是预处理。在这之前请允许我先向你介绍二分搜索：

二分搜索沿用了之前做递归的"Divide and Conquer"的思路，方法是这样的：

1. 定位到数据的中间，然后对比一下这个元素相比目标是更大还是更小？
2. 如果要查找的目标更大，那就抛弃更小的那一半数据，在更大的那一半查找，反之亦然。
3. 重复这样的过程，直到我们找到了最终结果。

这样的方法能拿到一个不错的$O(\log(n))$复杂度。但是这样的搜索方式有一个先决条件，那就是要处理的数据必须要先进行排序。这就是之前提到的预处理。

1
2
3
4
5
6
7
8
9
10

int binarySearch(int A[], int n, int x) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 避免溢出！
        if (A[mid] == x) return mid;
        else if (A[mid] < x) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // 没找到
}

    ⚠ 重要细节

为什么用 low + (high - low) / 2 而不是 (low + high) / 2？

因为当 low 和 high 都很大时，low + high 可能会整数溢出！这是面试和考试常问的点。

这样的要求导致我们在很多时候不会去使用二分搜索，因为对数据预先进行一步预处理可能更消耗时间。二分查找相比之下更适合用于静态数据，也就是一次写入，多次读取的情况。

1
2
3
4
5
6
7
8
9
10

// lower_bound: 返回第一个 >= x 的位置
int lower_bound(int A[], int n, int x) {
    int l = 0, r = n; // 注意是半开区间 [l, r)
    while (l < r) {
        int m = l + (r - l) / 2;
        if (A[m] < x) l = m + 1;
        else r = m;
    }
    return l;
}

数组的index由0至7，因此我们一共有$n=8$个元素. 要搜索的目标是$X=8$

直到Low指针位置与High发生相交，甚至相互跨越过去的时候，我们才能确定元素8根本不在数组里面。

跳转搜索 (Jump Search)

这就是那种典型的做题最爱算法。

跳转搜索 (跳转搜索) 有点像线性搜索，不过与其说像线性搜索那样一个一个往下遍历，跳转搜索会按大小为$k$的序列在目标数组里跳跃。过程大概是：

1. 按照这样的规律查找值：$0, k, 2k, 3k ...$
2. 当你发现跳过头的时候，回到上一次跳转的位置，然后从那里往后进行线性搜索。

$k$值的选择也是有讲究的。一般我们会选择让$k = \sqrt{n}$。

这就导致我们的时间复杂度是$O(\sqrt{n})$。

跳转搜索的执行效率没有二分搜索来的高效，但是在向后跳转成本很高的存储系统中（例如磁带），这种仅向前跳转的搜索算法还是比较有用处的。

假设我们已经有一个排好序的，大小为$n$的数组，你使用$k$作为跳转步长，那么你大概会需要完成这么多次比对来完成搜索：

$$\text{Total Comparisons} \approx \frac{n}{k} + k - 1$$

其中：

• $\frac{n}{k}$代表在最坏情况下，你找到目标属于的那个区块
• $k - 1$代表在最坏情况下，在区块内执行线性搜索的次数

“区块”就是我们每次执行跳转划分出来的区域。

嗯算就是了。

• $k = 5$:

$$\frac{n}{k} + k - 1 = \frac{100}{5} + 5 - 1 = 20 + 4 = 24$$

• $k = 20$:

$$\frac{n}{k} + k - 1 = \frac{100}{20} + 20 - 1 = 5 + 19 = 24$$

然后经过一波嗯算你发现他们的效率实际上相同。

插值搜索 (Interpolation Search)

你正在你的3000名微信好友名单里查找你想要找的人聊天，而是个人都会做的事情就是想一下你好友名字的音序，然后直接跳转到那个首字母来进行查找。

例如你想找罗永浩，你就去字母L那里开始找。

插值搜索的关键是按照要搜索的元素来估算它在有序数组里的位置：

$$\text{Position} = \text{Low} + \left\lfloor \frac{(X - A[\text{Low}]) \times (\text{High} - \text{Low})}{A[\text{High}] - A[\text{Low}]} \right\rfloor$$

这个公式的思路是：假设数据均匀分布，那么目标值在值域中的相对位置，应该和它在索引中的相对位置成正比。

插值搜索的平均表现是$O(\log(\log(n)))$，速度已经很快了！

但是插值搜索在有序平均分布的数据集上表现最好，因为我们的公式就假设元素是平均分布来计算位置的。如果你的数据不是均匀分布的，那么执行搜索的最坏复杂度就是$O(n)$。

我们使用这个公式：

$$ p = \text{low} + \left\lfloor \frac{(X - A[\text{low}]) \times (\text{high} - \text{low})}{A[\text{high}] - A[\text{low}]} \right\rfloor $$

代入数值：$\text{low} = 0$，$\text{high} = 9$，$X = 35$，$A[0] = 10$，$A[9] = 100$

$$p = 0 + \left\lfloor \frac{(35 - 10) \times (9 - 0)}{100 - 10} \right\rfloor = \left\lfloor \frac{25 \times 9}{90} \right\rfloor = \left\lfloor 2.5 \right\rfloor = 2$$

所以第一次会检查位置 $p = 2$，即 $A[2] = 30$。因为 $30 < 35$，下一轮会在 $[3, 9]$ 区间继续插值搜索。

范围搜索

那么假设我们想要进行范围搜索 (Range Search)，例如：找到夹在$X$和$Y$中间的所有值，你该如何制定策略？

首先我们决定不能使用哈希表来做。哈希函数的目标就是将值尽可能均匀，随机地散布在各处，所以即便你找到了一个元素，你也不能使用查找邻居的方式来快速定位范围。

有序数组 + 二分查找

如果数据是静态的（不需要频繁插入删除），最简单的方案就是：

1. 用 lower_bound(X) 找到第一个 $\geq X$ 的位置 $L$
2. 用 upper_bound(Y) 找到第一个 $> Y$ 的位置 $R$
3. 区间 $[L, R)$ 内的所有元素就是答案

1
2
3
4
5
6
7

// 范围查询：找出所有满足 X <= A[i] <= Y 的元素
int L = lower_bound(A, n, X);
int R = upper_bound(A, n, Y);
// A[L], A[L+1], ..., A[R-1] 即为结果
for (int i = L; i < R; i++) {
    printf("%d ", A[i]);
}

时间复杂度：$O(\log n + k)$，其中 $k$ 是结果数量。

动态数据的范围查询

如果数据需要频繁更新，可以考虑以下数据结构：

考试要点总结

    搜索算法复杂度速查

    ⚠ 考试常见陷阱

1. 二分搜索边界问题：low <= high vs low < high？取决于你用的是闭区间还是半开区间
2. mid 计算溢出：用 low + (high - low) / 2 而不是 (low + high) / 2
3. 插值搜索最坏情况：数据分布极不均匀时退化为 $O(n)$
4. 跳转搜索最优步长：$k = \sqrt{n}$，要会推导
5. 范围查询：知道 lower_bound 和 upper_bound 的区别和用法