Skip to content

约 6 分钟阅读

搜索算法 ​

搜索先要明确返回什么:一个匹配项、全部匹配位置、某个范围,还是一条可达路径。相同数据可以有不同索引;排序和建索引也有成本。选择算法时应一起考虑查询次数、更新频率、内存和底层访问方式。

例如订单时间戳按升序存为 [10,20,20,35,50],查询 [20,40) 需要返回索引区间 [1,4)。查到任意一个 20 不足以回答这个问题;需要找到第一个“不小于 20”和第一个“不小于 40”的位置。

二分查找上下界与半开查询范围

选索引前,先看查询合同 ​

查询场景合适入口成本与限制
无序小集合,偶尔找一次线性扫描最坏 O(n),无建索引成本;找到第一个后可停止
内存中的有序数组,多次范围查询二分上下界每个边界 O(log n) 比较,返回 k 项另需 O(k)
大量按订单编号精确查询哈希映射良好哈希与负载下平均 O(1),最坏可能 O(n),不直接提供有序范围
动态维护有序键平衡搜索树或有序索引查询通常 O(log n),普通未平衡 BST 可退化为链
磁盘上的索引范围数据库索引页访问、覆盖索引和回表影响实际成本,见数据库
文本中的连续子串内置查找、KMP 等字符串匹配另见字符串算法
节点之间的可达或最短路径DFS、BFS、Dijkstra 等先明确边权和图模型,见图算法

数组二分依赖 O(1) 随机访问。如果对链表反复定位中点,比较次数少也不等于总耗时 O(log n)。对一次无序查询,先用 O(n log n) 排序再二分,可能比直接扫描更慢。

二分的核心是排除范围 ​

以 lower_bound(values, target) 为例,它返回第一个不小于 target 的位置;不存在时返回 n。循环使用待搜索区间 [lo, hi),始终保持:

  • [0, lo) 中的值都小于 target。
  • [hi, n) 中的值都不小于 target。
  • 答案位置在闭区间 [lo, hi],可以等于 n。

若 values[mid] < target,mid 及其左侧不能是答案,令 lo=mid+1;否则 mid 仍可能是答案,令 hi=mid。每步严格缩小待检查区间,直到 lo=hi。

upper_bound 返回第一个严格大于 target 的位置。目标值全部出现的位置为 [lower_bound, upper_bound);半开时间范围 [start,end) 则使用两次 lower_bound。不要混淆这两种右边界。

完整实现:重复时间戳的范围查询 ​

以下 Python 3 程序的输入合同是已升序、可随机访问且比较关系一致的序列。查询期间不能修改。它不会每次用 O(n) 扫描验证有序性;调用方应在建索引时完成校验,避免把验证成本藏在 O(log n) 宣称中。

python
def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if target < values[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo


def range_indices(values, start, end):
    if end < start:
        raise ValueError("结束边界不能早于开始边界")
    return lower_bound(values, start), lower_bound(values, end)


times = (10, 20, 20, 35, 50)
order_ids = ("A", "B", "C", "D", "E")
lo, hi = range_indices(times, 20, 40)
assert (lo, hi) == (1, 4)
assert order_ids[lo:hi] == ("B", "C", "D")
assert (lower_bound(times, 20), upper_bound(times, 20)) == (1, 3)
assert range_indices((), 20, 40) == (0, 0)
assert range_indices(times, 20, 20) == (1, 1)
print(order_ids[lo:hi])

输出 ('B', 'C', 'D')。时间和编号数组属于同一个索引快照,必须保持位置对应。若原始记录无序,可以先按时间排序,再一次性构建两个数组;此后每次查询只查边界。Python 实际项目通常直接使用标准库 bisect_left、bisect_right,上述实现用于展示不变量。

每个边界查找最坏 O(log n) 次比较、O(1) 额外空间;返回 k 个编号的切片另外分配 O(k) 空间。排序预处理一般为 O(n log n),插入数组中间仍可能移动 O(n) 项。不能只用“二分 O(log n)”描述整个读写系统。

如果要精确查找一个值,先求 lower_bound,再检查位置小于 n 且该项等于目标;没有找到时返回明确的缺失结果。不要把插入位置直接当作已存在项下标。NaN、不同类型混合比较或排序键不一致会破坏比较合同,应在索引入口处理。

边界变化时,证明也要变化 ​

旋转有序数组不再满足全局升序,但在不含重复项等特定前提下,可以判断某一半有序并继续缩小范围。大量重复项会让这个判断失去信息,最坏可能需要线性扫描,不能无条件承诺 O(log n)。

峰值查找需定义是严格大于邻居还是允许相等,以及两端如何处理。空数组不能返回有效下标,平台状区域也不一定存在严格峰值。最近值查询则应先找插入位置,再比较其左右有效候选,并明确等距离时取哪一个。

“二分答案”搜索的对象是一个单调判断函数。例如确定批处理容量,使处理时间不超过限额,必须先证明容量增大时可行性只会单向变化,还要把一次判断的成本乘上迭代次数。存在并发抖动或非单调资源开销时,不能直接套用。

最长非递减子序列的 O(n log n) 实现会维护按长度组织的最小结尾值,并用 upper_bound 找更新位置;严格递增版本用 lower_bound。这个数组是用于推导长度的摘要,不一定就是原序列中的一条有效完整子序列;恢复路径还需要前驱信息。

哈希、树与路径搜索的常见误区 ​

哈希表的常数时间是有条件的平均或摊还结论。键必须遵守相等与哈希一致的合同,字符串哈希还与长度有关。开放寻址应限制最多探测槽位数,区分空槽与墓碑,删除后仍需继续查找;插入遇到墓碑不能立即停止查重,否则可能产生重复键。装满后必须扩容或返回失败,不能无限绕圈。

普通 BST 只保证搜索方向,不自动平衡。按升序插入可能退化到高度 n;范围查询要考虑输出 k 项,不能把存储整棵树的 O(n) 空间和单次查找的辅助空间混写。数据库 B+ 树还涉及页、扇出和叶链,不是只定义一个空节点类就完成了索引实现。

DFS 找到的是某条路径,不保证最短。BFS 在无权或等权图中按边数分层,通常在入队时标记已发现,避免同一节点重复排队;用前驱表恢复路径,可避免为每个队列项复制整条路径。顶点编号 0 是有效值,不能用 if not start 判断图为空。

A* 的 g+h 中,h 必须与移动规则和代价单位匹配。四方向单位代价网格可用曼哈顿距离;允许代价 √2 的斜向移动时,曼哈顿距离会高估直接斜走成本。关闭后不重开节点的实现还依赖一致性等前提。JPS 有特定网格与强制邻居规则,不能把部分跳跃函数、错误启发值及缺失的逐格路径恢复当作通用可运行实现。

验证搜索结果与索引生命周期 ​

上下界应与逐项扫描或标准库对照,覆盖空数组、单项、全部相等、目标在两端之外、重复值跨越中点、空范围和倒序范围。查到结果后,还应验证前一个位置确实不满足边界,当前位置满足边界;只比较某个样例下标容易漏掉 off-by-one。

上线前还要检查索引何时构建、如何原子切换快照、更新后是否可能读到“新时间数组配旧记录数组”。并发修改会使正确的二分代码返回错误业务记录。查询日志应区分未找到、输入非法、索引过期和服务异常,不能全部回退成空列表掩盖问题。

别急,先让缓存热一下。