查找算法

1. 概述与学习目标

1.1 什么是查找算法

查找（Search）是计算机科学中最基础、最频繁的操作之一——在数据集合中寻找满足特定条件的元素。Donald Knuth 在 The Art of Computer Programming Vol.3《Sorting and Searching》§6 中将查找分为四大类：

1. 顺序查找（§6.1 Sequential Searching）：无序数据上的线性扫描 $O(n)$；
2. 比较查找（§6.2 Searching by Comparison of Keys）：有序数据上的二分查找 $O(\log n)$、BST 查找 $O(\log n)$ 平均、平衡树查找 $O(\log n)$ 最坏、B 树查找 $O(\log_d n)$；
3. 数字查找（§6.3 Digital Searching）：基于键的数字/字符分解，如 Trie 树 $O(L)$；
4. 哈希查找（§6.4 Hashing）：基于哈希函数的直接寻址 $O(1)$ 平均。

查找算法分类树：
                            查找
                              |
        ┌────────────┬────────┴────────┬────────────┐
    顺序查找     比较查找           数字查找         哈希查找
    O(n)         O(log n)            O(L)             O(1) 平均
       │           │                   │                │
   哨兵优化   ┌────┴────┐           Trie 树        ┌────┴────┐
   O(n)      二分查找  树形查找      Radix Tree   链地址法   开放寻址
            O(log n)   │                          O(1)+     O(1)+
                       ├─ BST O(log n) 平均                   │
                       ├─ AVL O(log n) 最坏              线性探针
                       ├─ 红黑树 O(log n) 最坏           二次探针
                       ├─ B 树 O(log_d n)               双重哈希
                       └─ 跳表 O(log n) 期望
            ┌─ 插值查找 O(log log n) 平均
            └─ 斐波那契查找 O(log n)

特殊查找结构：

• 跳表（Skip List, Pugh 1990）：基于概率均衡的有序链表多层索引，$O(\log n)$ 期望查找；
• 布隆过滤器（Bloom Filter, Bloom 1970）：空间高效的概率查找结构，允许误判但不允许漏判；
• 字符串查找（KMP 1977、Boyer-Moore 1977、Rabin-Karp 1987）：在文本 $T[1..n]$ 中查找模式 $P[1..m]$ 的所有出现位置。

一句话定义：查找 = 在数据集合中定位满足条件的元素；顺序查找 $O(n)$ 通用于无序数据，二分查找 $O(\log n)$ 专精于有序静态数据，哈希查找 $O(1)$ 平均制霸精确匹配，平衡树与跳表 $O(\log n)$ 服务动态有序数据，布隆过滤器以 $O(1)$ 概率查找守护海量数据去重，KMP/Boyer-Moore 主宰字符串匹配。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆顺序查找 $O(n)$、二分查找 $O(\log n)$、插值查找 $O(\log \log n)$ 平均、哈希查找 $O(1)$ 平均、BST 查找 $O(\log n)$ 平均、跳表查找 $O(\log n)$ 期望的形式化复杂度，复述各查找算法在前提条件（有序性、随机访问、哈希函数、平衡性）上的差异；
2. 理解 Mauchly 1946 二分查找、Luhn 1953 IBM 备忘录哈希表、Bloom 1970 布隆过滤器（CACM 13(7):422-426）、Bayer-McCreight 1972 B 树（Acta Informatica 1(3):173-189）、Bayer 1972 对称二叉 B 树、Guibas-Sedgewick 1978 红黑树、Knuth-Morris-Pratt 1977 KMP（SIAM J. Comput. 6(2):323-350）、Boyer-Moore 1977 字符串匹配（CACM 20(10):762-772）、Pugh 1990 跳表（CACM 33(6):668-676）的历史脉络，说明不同查找结构的设计动机；
3. 应用顺序查找（含哨兵优化）、标准二分查找、二分查找变体（lower_bound、upper_bound、查找插入位置、旋转数组查找、二分答案、浮点二分）、插值查找、斐波那契查找编写可运行的 Python/C++/Java 代码，解决 LeetCode 33、35、69、162、240、34 等高频面试题；
4. 分析二分查找 $O(\log n)$ 复杂度的递推式 $T(n) = T(n/2) + O(1)$、插值查找 $O(\log \log n)$ 平均复杂度的概率分析、跳表 $O(\log n)$ 期望复杂度的几何分布论证、布隆过滤器误判率 $(1 - e^{-kn/m})^k$ 的数学推导，掌握”分治递推、概率分析、势能分析”三大核心论证方法；
5. 评估二分查找相对于顺序查找、哈希查找、BST 查找、跳表查找在”静态查找 vs 动态查找”、“精确匹配 vs 范围查询”、“内存开销 vs 查找速度”维度上的优劣，识别数据库 B+ 树索引、Redis 字典、Linux VMA 红黑树、浏览器历史、C++ std::map vs std::unordered_map 的选型动机；
6. 对比顺序查找、二分查找、插值查找、斐波那契查找、哈希查找、BST 查找、AVL/红黑树查找、B 树查找、跳表查找、Trie 查找在时间复杂度、空间复杂度、前提条件、是否支持范围查询、是否支持动态更新、缓存友好性维度的差异；
7. 创造性设计基于查找算法的开源项目解决方案，如数据库 B+ 树索引、Redis 字典与跳表双索引、布隆过滤器防缓存穿透、KMP/Boyer-Moore 文本编辑器查找、跳表实现 LRU 缓存、Trie 实现自动补全、哈希表实现去重统计。

1.3 术语表

1.4 查找算法全景对比

注：$n$ 为数据规模，$m$ 为模式串长度，$L$ 为键长，$\Sigma$ 为字符集大小，$k$ 为哈希函数个数。

1.5 适用场景与不适用场景

跨模块引用：二分查找基于有序数组，参见 数组与动态数组；哈希查找的底层结构参见 哈希表；BST/AVL/红黑树/B 树的详细实现参见 树 与 平衡树与高级树；跳表的详细实现参见 跳跃表；并查集的查找参见 并查集；堆作为优先队列的查找极值参见 堆与优先队列；字符串查找的深入讨论参见 字符串算法。

2. 历史动机与演进

2.1 前查找时代：从纸质索引到内存查找

19 世纪末，图书馆学与统计学已发展出大量”索引”技术：图书目录卡、人口普查穿孔卡片、电话簿。这些物理索引的关键问题是：给定一个关键字，如何在大量数据中快速定位？

1928 年Mechanical World首次记载了用机器辅助查找穿孔卡片的方法，但仅限于顺序查找。直到 1946 年，二分查找的思想才在计算机科学文献中正式出现。

2.2 Mauchly 1946：二分查找的诞生

1946 年，John Mauchly（ENIAC 联合设计者）在 Moore School Lectures《Sorting and Collating》中首次公开描述二分查找算法：

给定一个有序数组 $A[1..n]$，将目标 $x$ 与中间元素 $A[\lfloor n/2 \rfloor]$ 比较；若相等则返回，若 $x$ 较小则递归在左半查找，否则在右半查找。

但 Mauchly 的描述并不完整，未明确边界处理。1962 年Hermann Bottenbruch在Communications of the ACM给出首个被广泛认可的完整实现。Knuth 在 TAOCP Vol.3 §6.2.1 考据后写道：

“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky, and many programmers have gotten it wrong over the years.”

这一预言在 2006 年被 Joshua Bloch 印证。

2.3 Joshua Bloch 2006：二分查找的”千年 Bug”

2006 年，Google 研究员 Joshua Bloch（前 Sun Microsystems Java 标准库首席工程师）在博客发表《Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken》，公开指出 Java 标准库 java.util.Arrays.binarySearch 存在整数溢出 Bug：

// Bug 版本（Java 标准库至 JDK 5）
int mid = (low + high) / 2;   // 当 low + high > Integer.MAX_VALUE 时溢出为负数

Bug 追溯到 Jon Bentley 1986 年《Programming Pearls》中的二分查找实现——Bentley 在书中将该实现作为”经过验证的正确代码”展示，但 2006 年 Bloch 的发现证明该代码在 $n > 2^{30}$ 时会崩溃。修复方案：

int mid = low + (high - low) / 2;       // 加法改为减法避免溢出
// 或
int mid = (low + high) >>> 1;           // 无符号右移

这一事件成为软件工程史上的经典案例，证明”简单的算法不一定容易实现正确”。

2.4 Luhn 1953：哈希表的诞生

1953 年 1 月，IBM 的 Hans Peter Luhn 在内部备忘录中首次提出”哈希函数 + 链地址法”的查找方案。Luhn 当时研究 IBM 701 计算机的快速检索问题，提出：

• 用哈希函数 $h(k)$ 将键 $k$ 映射到数组下标；
• 冲突时用链表链接（链地址法，chaining）。

这是链式线性表首次应用。Luhn 因此获 1956 年 IBM Outstanding Contribution Award。

1968 年，Bob Morris 在Communications of the ACM 11(1):38-43《Scatter Storage Techniques》系统化哈希理论，引入开放寻址法（open addressing）、线性探查（linear probing）、二次探查（quadratic probing）等冲突解决技术。Knuth TAOCP Vol.3 §6.4（1973）给出权威论述与对比分析。

2.5 Bloom 1970：布隆过滤器

1970 年，Burton Howard Bloom 在Communications of the ACM 13(7):422-426《Space/Time Trade-offs in Hash Coding with Allowable Errors》中提出布隆过滤器。Bloom 当时在 Computer Usage Corporation 研究海量数据的快速去重问题，提出：

• 用 $m$ 位位数组 + $k$ 个独立哈希函数；
• 插入：将 $k$ 个哈希位置全部置 1；
• 查询：若 $k$ 个位置全为 1，则元素可能存在；若有任何 0，则元素一定不存在；
• 误判率约 $(1 - e^{-kn/m})^k$。

布隆过滤器以 $O(m \text{ bits})$ 空间高效著称，是大数据时代缓存穿透防护、URL 去重、Cassandra HINT、PostgreSQL bloom 索引的核心。

2.6 Bayer-McCreight 1972：B 树与磁盘索引

1970 年，Boeing Scientific Research Labs 的 Rudolf Bayer 与 Edward M. McCreight 在研究大型磁盘文件的索引时，发现二叉树高度过大、磁盘 IO 次数过多。1972 年他们在Acta Informatica 1(3):173-189 发表《Organization and Maintenance of Large Ordered Indices》，提出 B 树：

• 每节点最多 $2t-1$ 个关键字、$2t$ 个子节点（$t$ 为最小度数）；
• 根节点到叶节点等长（完美平衡）；
• 查找、插入、删除均 $O(\log_t n)$；
• 通过增大 $t$（典型 50-500），树高通常 3-4 即可表示数十亿关键字。

B 树是 MySQL InnoDB、PostgreSQL、Oracle、SQL Server、SQLite 等所有关系数据库索引的基石。B+ 树（Bayer 1972 后续工作）将数据仅存叶节点，叶节点用链表连接，使范围查询 $O(\log_t n + k)$。

McCreight 在 2010 年 PODS 大会访谈中曾回忆：“B-tree 是 Bayer-B-tree 也是 Boeing-B-tree 也是 Balanced-B-tree 也可能是 Broad-B-tree，但我们从未在论文中明确解释 B 的含义。“

2.7 Bayer 1972 / Guibas-Sedgewick 1978：红黑树

1972 年，Rudolf Bayer 在Acta Informatica 1(4):290-306 发表《Symmetric binary B-trees: Data structure and maintenance algorithms》，提出对称二叉 B 树（symmetric binary B-tree, SB-tree）——用颜色标记模拟 B 树的二叉结构。这是红黑树的雏形。

1978 年，Leonidas J. Guibas 与 Robert Sedgewick 在 FOCS 论文《A Dichromatic Framework for Balanced Trees》中重新形式化 SB-tree，正式命名红黑树（red-black tree），并简化插入删除的旋转操作。Sedgewick 在 Xerox PARC 的彩色显示器上选择”红色”作为视觉最易辨识的颜色（PARC 当时是少数有彩色显示器的实验室）。

红黑树的 5 条性质保证高度 $\leq 2\log(n+1)$，使所有操作 $O(\log n)$ 最坏。红黑树被广泛采用：C++ STL std::map/std::set、Java TreeMap/TreeSet、Linux kernel CFS 调度器、Linux VMA 内存管理、Nginx timer、epoll 内部。

2.8 Knuth-Morris-Pratt 1977 与 Boyer-Moore 1977：字符串查找双星

1977 年是字符串查找算法的”奇迹年”。当年同时发表两篇里程碑论文：

KMP 算法（Knuth-Morris-Pratt）：

• Donald Knuth（斯坦福）、James H. Morris（CMU，研究字符串匹配硬件）、Vaughan Pratt（MIT）三人独立发现；
• 1977 年联合发表于 SIAM Journal on Computing 6(2):323-350《Fast Pattern Matching in Strings》；
• 核心思想：预处理模式串构造 next 数组（部分匹配表），使匹配失败时不回退文本指针；
• 复杂度：$O(n+m)$ 时间、$O(m)$ 空间，最坏线性。

Boyer-Moore 算法：

• Robert S. Boyer 与 J. Strother Moore 在 SRI International 研究定理证明器时提出；
• 1977 年发表于 Communications of the ACM 20(10):762-772《A Fast String Searching Algorithm》；
• 核心思想：从模式串右端开始匹配，结合坏字符规则与好后缀规则使模式串能跳跃式前进；
• 平均复杂度 $O(n/m)$（亚线性！），最坏 $O(nm)$（启发式无 worst-case 保证）；
• 实践中 Boyer-Moore 通常是字符串查找最快的算法，被 grep、PostgreSQL、各种文本编辑器 Ctrl+F 采用。

1987 年 Karp-Rabin 在 IBM Journal of Research and Development 31(2):249-260《Efficient randomized pattern-matching algorithms》提出Rabin-Karp 算法，用滚动哈希实现 $O(n+m)$ 平均、$O(nm)$ 最坏的字符串查找，是后续 Rabin-Karp 指纹、二维模式匹配的基础。

2.9 Pugh 1990：跳表

1990 年，马里兰大学 William Pugh 在 Communications of the ACM 33(6):668-676 发表《Skip Lists: A Probabilistic Alternative to Balanced Trees》，提出跳表（Skip List）：

• 在有序链表上随机添加多层索引；
• 第 $i$ 层节点以概率 $p$（通常 0.5 或 0.25）出现在第 $i+1$ 层；
• 查找：从最高层开始，每层线性前进，遇大则下降一层；
• 期望查找 $O(\log n)$、期望插入 $O(\log n)$、期望删除 $O(\log n)$；
• 实现远比红黑树简单（约 100 行 C 代码 vs 红黑树 500+ 行）。

Pugh 在论文中写道：“Skip lists are a probabilistic alternative to balanced trees. They are easy to implement and are at least as efficient as balanced trees.”

跳表被广泛采用：Redis zset（zskiplist）、LevelDB/RocksDB MemTable、MongoDB WiredTiger、MemSQL、skiplist-based LRU。Redis 作者 antirez 在博客中明确表示：“Skip lists are a data structure that I have always found fascinating. They are simple, elegant, and they work.”

2.10 查找算法演进时间线

timeline
    title 查找算法演进时间线
    1946 : Mauchly 公开描述二分查找
         : Moore School Lectures《Sorting and Collating》
    1953 : Luhn 在 IBM 内部备忘录提出哈希表
         : 链地址法（chaining）
    1957 : Peterson 发表《Addressing for Random Access Storage》
         : 插值查找 + 哈希存储系统化
    1962 : Bottenbruch 在 CACM 给出二分查找首个完整实现
    1968 : Bob Morris《Scatter Storage Techniques》系统化哈希
         : 开放寻址、线性探查、二次探查
    1970 : Bloom 在 CACM 13(7):422-426 提出布隆过滤器
         : 概率查找结构诞生
    1972 : Bayer-McCreight 在 Acta Informatica 1(3):173-189 发表 B 树
         : Bayer 同年发表对称二叉 B 树（红黑树雏形）
    1973 : Knuth 出版 TAOCP Vol.3《Sorting and Searching》
         : 查找算法系统化（§6.1-6.4）
    1977 : KMP 发表于 SIAM J. Comput. 6(2):323-350
         : Boyer-Moore 发表于 CACM 20(10):762-772
         : 字符串查找双星诞生
    1978 : Guibas-Sedgewick《A Dichromatic Framework for Balanced Trees》
         : 红黑树正式命名与简化
    1987 : Karp-Rabin《Efficient randomized pattern-matching algorithms》
         : Rabin-Karp 滚动哈希
    1990 : Pugh《Skip Lists: A Probabilistic Alternative to Balanced Trees》
         : CACM 33(6):668-676
         : 跳表诞生，Redis/LevelDB 后续采用
    2006 : Joshua Bloch 公开 Java 标准库二分查找整数溢出 Bug
         : 印证 Knuth "二分查找 60 年仍常错"论断
    2010s : 布隆过滤器在 Cassandra/PostgreSQL/HBase 大规模应用
         : 跳表在 Redis/LevelDB/RocksDB/MongoDB 全面采用

2.11 关键设计决策

3. 形式化定义

3.1 查找问题的形式化定义

查找问题：给定关键字集合 $S = \{k_1, k_2, \ldots, k_n\}$（可能有序或无序）与查询关键字 $x$，查找问题分为三种：

1. 精确查找（Exact Search）：返回 $k \in S$ 使得 $k = x$，或报告不存在；
2. 范围查找（Range Search）：返回 $\{k \in S : a \leq k \leq b\}$；
3. 前驱/后继查找（Predecessor/Successor）：返回 $\max\{k \in S : k \leq x\}$ 或 $\min\{k \in S : k \geq x\}$。

符号表 ADT（Symbol Table / Dictionary）：

3.2 二分查找的形式化定义

前提条件：数组 $A[0..n-1]$ 满足有序性（monotonicity）：$\forall i < j, A[i] \leq A[j]$（升序）。

循环不变式（Loop Invariant）：在二分查找循环的每次迭代开始时，若 $x \in A$，则 $x \in A[\text{left}..\text{right}]$。

正确性证明：

1. 初始化：$\text{left} = 0, \text{right} = n - 1$，$x \in A[0..n-1]$ 显然成立；
2. 保持：每次迭代计算 $\text{mid} = \lfloor (\text{left} + \text{right}) / 2 \rfloor$：
   • 若 $A[\text{mid}] = x$，返回 $\text{mid}$，循环结束；
   • 若 $A[\text{mid}] < x$，则 $x \notin A[\text{left}..\text{mid}]$（由有序性），故 $x \in A[\text{mid}+1..\text{right}]$，令 $\text{left} = \text{mid} + 1$；
   • 若 $A[\text{mid}] > x$，类似地令 $\text{right} = \text{mid} - 1$； 不变式保持；
3. 终止：当 $\text{left} > \text{right}$ 时循环终止，此时区间为空，故 $x \notin A$。

3.3 哈希查找的形式化定义

哈希函数：$h: U \to \{0, 1, \ldots, m-1\}$，将键域 $U$ 映射到 $m$ 个桶。

简单一致哈希（Simple Uniform Hashing）：$\forall k \in U$，$h(k)$ 独立均匀分布于 $\{0, 1, \ldots, m-1\}$。

负载因子：$\alpha = n / m$，其中 $n$ 为元素数、$m$ 为桶数。

冲突（Collision）：$\exists k_1 \neq k_2, h(k_1) = h(k_2)$。由鸽巢原理，当 $n > m$ 时冲突不可避免。

冲突解决：

• 链地址法（Chaining）：桶 $i$ 维护链表，存储所有 $h(k) = i$ 的键；
• 开放寻址（Open Addressing）：冲突时按探查序列 $h(k, 0), h(k, 1), \ldots$ 寻找空桶。

3.4 跳表的形式化定义

跳表由 $L$ 层链表组成，$L$ 是随机变量。每个节点在第 $i$ 层出现的概率为 $p^{i-1}$（$p$ 通常 0.5）。

期望层高：$E[L] = \log_{1/p} n = \log_2 n$（$p = 0.5$ 时）。

期望查找路径长度：每层期望前进 2 步，故总期望比较次数 $\leq 2 \log_{1/p} n$。

3.5 布隆过滤器的形式化定义

• 位数组 $B[0..m-1]$，初始全为 0；
• $k$ 个独立哈希函数 $h_1, h_2, \ldots, h_k: U \to \{0, 1, \ldots, m-1\}$；
• 插入 $x$：$\forall i \in [1, k], B[h_i(x)] = 1$；
• 查询 $x$：返回 $\bigwedge_{i=1}^{k} B[h_i(x)]$（即所有 $h_i(x)$ 位置均为 1）。

误判率推导：插入 $n$ 个元素后，某一位仍为 0 的概率为 $(1 - 1/m)^{kn} \approx e^{-kn/m}$。查询一个不在集合中的元素时，$k$ 个哈希位置全为 1 的概率为： $P_{\text{fp}} = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx \left(1 - e^{-kn/m}\right)^k$

最优 $k = (m/n) \ln 2$ 时，误判率最小为 $(0.6185)^{m/n}$。

4. 顺序查找

4.1 基本思想

顺序查找（Sequential Search / Linear Search）是最简单的查找算法：从数组第一个元素开始，逐个与目标比较，直到找到或遍历完毕。

4.2 标准实现

Python 实现：

def sequential_search(arr: list[int], target: int) -> int:
    """顺序查找：返回 target 在 arr 中的索引，不存在返回 -1
    
    Args:
        arr: 待查找数组（无需有序）
        target: 目标值
    
    Returns:
        int: target 的索引，或 -1
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

C++ 实现：

#include <vector>
#include <algorithm>

// 顺序查找：返回 target 在 arr 中的索引，不存在返回 -1
int sequentialSearch(const std::vector<int>& arr, int target) {
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

// C++ STL 标准库提供 std::find，返回迭代器
auto it = std::find(arr.begin(), arr.end(), target);
if (it != arr.end()) {
    int index = std::distance(arr.begin(), it);
}

Java 实现：

// 顺序查找：返回 target 在 arr 中的索引，不存在返回 -1
public static int sequentialSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

4.3 哨兵优化

哨兵优化通过在数组末尾放置目标值，省去每次循环的边界检查 i < n，将每次迭代的 2 次比较降为 1 次：

def sentinel_search(arr: list[int], target: int) -> int:
    """哨兵顺序查找：用末尾哨兵省去边界检查
    
    注意：原数组会被临时修改，最后恢复
    """
    n = len(arr)
    if n == 0:
        return -1
    last = arr[n - 1]
    arr[n - 1] = target  # 设置哨兵
    
    i = 0
    while arr[i] != target:
        i += 1
    
    arr[n - 1] = last  # 恢复末尾
    if i < n - 1 or last == target:
        return i
    return -1

int sentinelSearch(std::vector<int>& arr, int target) {
    int n = static_cast<int>(arr.size());
    if (n == 0) return -1;
    int last = arr[n - 1];
    arr[n - 1] = target;
    
    int i = 0;
    while (arr[i] != target) ++i;
    
    arr[n - 1] = last;
    if (i < n - 1 || last == target) return i;
    return -1;
}

4.4 复杂度分析

适用场景：数据无序；数据规模小（$n < 32$）；仅一次性查找；底层是链表等不支持随机访问的结构。

5. 二分查找

5.1 核心思想

二分查找（Binary Search）要求数组有序且支持随机访问，每次将查找区间减半：

在 [1, 3, 5, 7, 9, 11, 13, 15] 中查找 7：

第1轮: [1, 3, 5, 7, 9, 11, 13, 15]  mid=4, arr[4]=9 > 7 → 左半
第2轮: [1, 3, 5, 7]                  mid=1, arr[1]=3 < 7 → 右半
第3轮: [5, 7]                        mid=2, arr[2]=5 < 7 → 右半
第4轮: [7]                           mid=3, arr[3]=7 = 7 → 找到!

5.2 标准实现（闭区间 [left, right]）

Python 实现：

def binary_search(arr: list[int], target: int) -> int:
    """标准二分查找（闭区间 [left, right]）
    
    Args:
        arr: 有序数组（升序）
        target: 目标值
    
    Returns:
        int: target 的索引，不存在返回 -1
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        # 防止整数溢出：用减法而非加法
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

C++ 实现：

// 标准二分查找（闭区间 [left, right]）
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = static_cast<int>(arr.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Java 实现：

// 标准二分查找（闭区间 [left, right]）
public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

5.3 防止整数溢出

计算 mid 时，(left + right) / 2 在 left + right 超过 Integer.MAX_VALUE（$2^{31}-1$）时会溢出为负数，导致数组越界。

//  危险：当 left + right > Integer.MAX_VALUE 时溢出
int mid = (left + right) / 2;

//  正确写法 1：减法
int mid = left + (right - left) / 2;

//  正确写法 2：无符号右移（仅 Java/C++）
int mid = (left + right) >>> 1;  // Java，自动处理溢出

//  正确写法 3：长整型
int mid = (int) ((long) left + (long) right) / 2;

Bug 历史：Jon Bentley 1986《Programming Pearls》中的二分查找实现包含此 Bug，Joshua Bloch 2006 年发现 Java 标准库 Arrays.binarySearch 也继承了此 Bug（JDK 5 及更早），从 JDK 6 开始修复。这是软件工程史上最著名的”千年 Bug”之一。

5.4 复杂度分析

时间复杂度推导：

设 $T(n)$ 为长度 $n$ 的数组二分查找的时间，则：

$T(n) = T(n/2) + O(1)$

由主定理（Master Theorem）$a = 1, b = 2, f(n) = O(1) = O(n^0)$，故 $T(n) = O(\log n)$。

比较次数：$n$ 个元素最多比较 $\lfloor \log_2 n \rfloor + 1$ 次。

二分查找是对数级算法，即使数据规模达到 $10^{18}$，也仅需 60 次比较。

空间复杂度：$O(1)$（迭代版本）；$O(\log n)$（递归版本，递归栈深度）。

6. 二分查找变体

6.1 lower_bound（第一个 ≥ target 的位置）

def lower_bound(arr: list[int], target: int) -> int:
    """返回第一个 >= target 的位置（半开区间 [left, right)）"""
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # arr[mid] >= target，收缩右边界
    return left  # left 是第一个 >= target 的位置

// C++ STL 直接提供 std::lower_bound
#include <algorithm>
auto it = std::lower_bound(arr.begin(), arr.end(), target);
int index = std::distance(arr.begin(), it);

// Java：手动实现（标准库 Arrays.binarySearch 不直接提供 lower_bound）
public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

Python bisect 模块：

import bisect

arr = [1, 2, 2, 2, 3, 4, 5]
target = 2

# 第一个 >= target 的位置（即 lower_bound）
pos = bisect.bisect_left(arr, target)  # 1

# 第一个 > target 的位置（即 upper_bound）
pos = bisect.bisect_right(arr, target)  # 4

6.2 upper_bound（第一个 > target 的位置）

def upper_bound(arr: list[int], target: int) -> int:
    """返回第一个 > target 的位置"""
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left  # left 是第一个 > target 的位置

6.3 查找插入位置（LeetCode 35）

def search_insert(nums: list[int], target: int) -> int:
    """返回 target 应插入的位置（保持有序）"""
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

6.4 查找旋转排序数组（LeetCode 33）

旋转排序数组如 [4, 5, 6, 7, 0, 1, 2]（原数组 [0, 1, 2, 4, 5, 6, 7] 在索引 3 处旋转）。核心思想：每次二分后判断哪半边有序，再判断 target 是否在有序半边内：

def search_rotated(nums: list[int], target: int) -> int:
    """旋转排序数组查找（LeetCode 33）"""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        
        # 判断哪半边有序
        if nums[left] <= nums[mid]:  # 左半边有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半边有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

6.5 二分答案（搜索答案空间）

当问题满足单调性——答案越大越容易（或越难）满足条件——可以对答案空间二分搜索：

def split_array(nums: list[int], m: int) -> int:
    """分割数组的最大值（LeetCode 410）
    
    将数组分成 m 个连续子数组，最小化最大子数组和
    单调性：max_sum 越大，所需分组数越少
    """
    def can_split(max_sum: int) -> bool:
        count, current = 1, 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = num
            else:
                current += num
        return count <= m
    
    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid  # 答案可行，尝试更小
        else:
            left = mid + 1  # 答案不可行，必须更大
    return left

二分答案模板：

def binary_search_answer():
    left, right = lower_bound, upper_bound
    while left < right:
        mid = left + (right - left) // 2
        if check(mid):  # check 是单调的：x 越大越容易满足
            right = mid  # 或 left = mid（取决于单调方向）
        else:
            left = mid + 1
    return left

6.6 浮点数二分

def my_sqrt(x: float, epsilon: float = 1e-7) -> float:
    """浮点数二分求平方根"""
    if x < 0:
        raise ValueError("Cannot compute square root of negative number")
    if x == 0:
        return 0.0
    left, right = 0.0, max(1.0, x)
    while right - left > epsilon:
        mid = (left + right) / 2
        if mid * mid < x:
            left = mid
        else:
            right = mid
    return (left + right) / 2

# 固定迭代次数版本（避免浮点精度导致的死循环）
def my_sqrt_iter(x: float, iterations: int = 100) -> float:
    left, right = 0.0, max(1.0, x)
    for _ in range(iterations):
        mid = (left + right) / 2
        if mid * mid < x:
            left = mid
        else:
            right = mid
    return (left + right) / 2

6.7 两大模板总结

模板一：闭区间 [left, right]

left, right = 0, len(arr) - 1
while left <= right:
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
return -1

模板二：半开区间 [left, right)

left, right = 0, len(arr)
while left < right:
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid
return left  # 第一个 >= target 的位置

选择指南：

7. 插值查找

7.1 核心思想

二分查找每次固定取中点 $\text{mid} = \lfloor (\text{left} + \text{right}) / 2 \rfloor$，但当数据均匀分布时，可以根据目标值的大小估算其位置：

$\text{mid} = \text{left} + \frac{(\text{target} - A[\text{left}]) \times (\text{right} - \text{left})}{A[\text{right}] - A[\text{left}]}$

类比查字典：找 “apple” 会翻到前面，找 “zoo” 会翻到后面，而不是每次翻到中间。

7.2 实现

def interpolation_search(arr: list[int], target: int) -> int:
    """插值查找：适用于均匀分布的有序数据
    
    平均复杂度 O(log log n)，最坏 O(n)
    """
    left, right = 0, len(arr) - 1
    
    while left <= right and arr[left] <= target <= arr[right]:
        # 防止除零
        if arr[left] == arr[right]:
            return left if arr[left] == target else -1
        
        # 插值公式
        mid = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
        
        # 边界检查（防止 mid 越界）
        if mid < left or mid > right:
            break
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

public static int interpolationSearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right && target >= arr[left] && target <= arr[right]) {
        if (arr[left] == arr[right]) {
            return arr[left] == target ? left : -1;
        }
        int mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);
        if (mid < left || mid > right) break;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

7.3 复杂度分析

平均复杂度 $O(\log \log n)$ 推导（Peterson 1957）：

假设 $A$ 在 $[A[\text{left}], A[\text{right}]]$ 上均匀分布，则每次插值后，剩余区间长度的期望为 $\sqrt{n}$（并非精确 $\sqrt{n}$，但量级如此）。设 $T(n)$ 为查找时间，则：

$T(n) \approx T(\sqrt{n}) + O(1)$

令 $n = 2^{2^k}$，则 $\sqrt{n} = 2^{2^{k-1}}$，递归 $k$ 次后 $n = 2$，故 $T(n) = O(k) = O(\log \log n)$。

适用场景：数据量大且分布均匀的有序表，如年龄表、成绩表、时间戳表。

8. 斐波那契查找

8.1 核心思想

斐波那契查找（Fibonacci Search）利用 Fibonacci 数列对有序表进行黄金分割，与二分查找的等分（1:1）不同：

• 二分查找：$\text{mid} = (\text{left} + \text{right}) / 2$
• 斐波那契查找：$\text{mid} = \text{left} + F[k-1] - 1$

其中 $F[k]$ 是大于等于数组长度的最小 Fibonacci 数。

Fibonacci 数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

核心分割：
长度 F[k]-1 的数组分为：
  左子数组: F[k-1]-1 个元素
  中间元素: 1 个
  右子数组: F[k-2]-1 个元素
  满足恒等式: F[k]-1 = (F[k-1]-1) + 1 + (F[k-2]-1)

8.2 实现

def fibonacci_search(arr: list[int], target: int) -> int:
    """斐波那契查找：用黄金分割替代等分"""
    n = len(arr)
    if n == 0:
        return -1
    
    # 生成 Fibonacci 数列
    fib = [1, 1]
    while fib[-1] < n:
        fib.append(fib[-1] + fib[-2])
    
    k = len(fib) - 1
    
    # 扩展数组到 F[k]-1 长度，用末尾元素填充
    temp = arr + [arr[-1]] * (fib[k] - 1 - n)
    
    left, right = 0, n - 1
    while left <= right:
        mid = left + fib[k - 1] - 1
        if temp[mid] == target:
            return min(mid, n - 1)  # 处理填充位置
        elif temp[mid] < target:
            left = mid + 1
            k -= 2  # 右子数组长度为 F[k-2]-1
        else:
            right = mid - 1
            k -= 1  # 左子数组长度为 F[k-1]-1
    
    return -1

public static int fibonacciSearch(int[] arr, int target) {
    int n = arr.length;
    if (n == 0) return -1;
    
    // 生成 Fibonacci 数列
    int[] fib = new int[n + 2];
    fib[0] = fib[1] = 1;
    int k = 1;
    while (fib[k] < n) {
        k++;
        fib[k] = fib[k - 1] + fib[k - 2];
    }
    
    // 扩展数组
    int[] temp = Arrays.copyOf(arr, fib[k] - 1);
    for (int i = n; i < temp.length; i++) {
        temp[i] = arr[n - 1];
    }
    
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + fib[k - 1] - 1;
        if (temp[mid] == target) {
            return Math.min(mid, n - 1);
        } else if (temp[mid] < target) {
            left = mid + 1;
            k -= 2;
        } else {
            right = mid - 1;
            k -= 1;
        }
    }
    return -1;
}

8.3 与二分查找对比

优势场景：对除法运算敏感的硬件（嵌入式、早期 CPU）；硬件除法指令慢于加减法时。

实际工程：现代 CPU 除法已快（3-20 周期），斐波那契查找的优势不明显，实际工程中很少使用。

9. 哈希查找

9.1 核心思想

哈希查找（Hash Search）通过哈希函数 $h(k)$ 将键直接映射到数组下标，实现 $O(1)$ 平均查找：

key "alice" → hash function h() → index 42 → bucket[42]

冲突解决：
1. 链地址法：bucket[42] = LinkedList[(alice, 100), (bob, 85)]
2. 开放寻址：bucket[42] 冲突 → 探查 bucket[43], bucket[44], ...

9.2 哈希函数设计

好的哈希函数应满足：

1. 一致性：$k_1 = k_2 \Rightarrow h(k_1) = h(k_2)$；
2. 均匀性：$h(k)$ 均匀分布于 $[0, m)$；
3. 高效性：计算 $O(1)$。

常见哈希函数：

• 除留余数法（Division Method）：$h(k) = k \bmod m$，$m$ 选素数；
• 乘法哈希（Multiplication Method）：$h(k) = \lfloor m \cdot (kA \bmod 1) \rfloor$，$A = (\sqrt{5} - 1) / 2$；
• MurmurHash：Austin Appleby 2008，广泛用于 Redis、Cassandra；
• CityHash / FarmHash：Google 2011/2014，用于 Bigtable、Spanner；
• xxHash：Yann Collet 2012，目前最快的非加密哈希之一。

9.3 冲突解决

链地址法（Chaining）：

class HashTableChaining:
    def __init__(self, capacity: int = 16):
        self._capacity = capacity
        self._buckets: list[list[tuple]] = [[] for _ in range(capacity)]
        self._size = 0
    
    def _hash(self, key) -> int:
        return hash(key) % self._capacity
    
    def insert(self, key, value) -> None:
        idx = self._hash(key)
        for i, (k, _) in enumerate(self._buckets[idx]):
            if k == key:
                self._buckets[idx][i] = (key, value)
                return
        self._buckets[idx].append((key, value))
        self._size += 1
    
    def search(self, key):
        idx = self._hash(key)
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

开放寻址法（Open Addressing）——线性探查：

class HashTableOpenAddressing:
    def __init__(self, capacity: int = 16):
        self._capacity = capacity
        self._keys: list = [None] * capacity
        self._values: list = [None] * capacity
        self._size = 0
        self._DELETED = object()  # 哨兵表示已删除
    
    def _hash(self, key) -> int:
        return hash(key) % self._capacity
    
    def _probe(self, key, for_insert: bool = False):
        """线性探查：返回 key 应在的位置"""
        idx = self._hash(key)
        for i in range(self._capacity):
            j = (idx + i) % self._capacity
            if self._keys[j] is None or (for_insert and self._keys[j] is self._DELETED):
                return j
            if self._keys[j] == key:
                return j
        raise RuntimeError("Hash table full")
    
    def insert(self, key, value) -> None:
        if self._size >= self._capacity * 0.7:  # 负载因子阈值
            self._resize()
        idx = self._probe(key, for_insert=True)
        if self._keys[idx] != key:
            self._size += 1
        self._keys[idx] = key
        self._values[idx] = value
    
    def search(self, key):
        idx = self._hash(key)
        for i in range(self._capacity):
            j = (idx + i) % self._capacity
            if self._keys[j] is None:
                raise KeyError(key)
            if self._keys[j] == key:
                return self._values[j]
        raise KeyError(key)

9.4 复杂度分析

链地址法：

开放寻址（$\alpha < 1$）：

多语言实现：

# Python dict 是哈希表
d = {"alice": 100, "bob": 85}
d["charlie"] = 92  # O(1) 平均
print(d.get("alice"))  # O(1) 平均

// C++ std::unordered_map 是哈希表
#include <unordered_map>
std::unordered_map<std::string, int> m;
m["alice"] = 100;  // O(1) 平均
m.find("alice");    // O(1) 平均

// std::map 是红黑树（有序）
#include <map>
std::map<std::string, int> om;
om["alice"] = 100;  // O(log n)
om.find("alice");    // O(log n)

// Java HashMap 是哈希表（Java 8+ 链表长度 > 8 转红黑树）
import java.util.HashMap;
HashMap<String, Integer> m = new HashMap<>();
m.put("alice", 100);  // O(1) 平均
m.get("alice");        // O(1) 平均

// TreeMap 是红黑树
import java.util.TreeMap;
TreeMap<String, Integer> om = new TreeMap<>();
om.put("alice", 100);  // O(log n)

10. 树形查找

10.1 二叉搜索树（BST）查找

BST 性质：对每个节点 $x$，左子树所有节点 $\leq x.\text{key}$，右子树所有节点 $\geq x.\text{key}$。

class TreeNode:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

def bst_search(root: TreeNode, key):
    """BST 查找：平均 O(log n)，最坏 O(n)（链式退化）"""
    while root is not None:
        if key == root.key:
            return root
        elif key < root.key:
            root = root.left
        else:
            root = root.right
    return None

复杂度：

• 平均（随机插入）：$O(\log n)$
• 最坏（有序插入导致链式退化）：$O(n)$

10.2 平衡树查找（AVL / 红黑树）

AVL 树（Adelson-Velsky and Landis 1962）：每个节点左右子树高度差 $\leq 1$，保证 $O(\log n)$ 最坏。

红黑树（Bayer 1972, Guibas-Sedgewick 1978）：5 条性质保证高度 $\leq 2\log(n+1)$。

红黑树 5 条性质：

1. 每个节点是红色或黑色；
2. 根节点是黑色；
3. 每个叶节点（NIL）是黑色；
4. 红节点的子节点都是黑色（不能有连续红节点）；
5. 从任一节点到其所有叶节点的路径包含相同数目的黑节点。

查找代码与 BST 完全相同，平衡性由插入/删除时的旋转与重新着色维护：

def rb_search(root: TreeNode, key):
    """红黑树查找：O(log n) 最坏"""
    return bst_search(root, key)  # 查找代码与 BST 相同

工业应用：

• C++ std::map / std::set / std::multimap / std::multiset：红黑树
• Java TreeMap / TreeSet：红黑树
• Linux kernel CFS 调度器：红黑树（按 vruntime 排序）
• Linux kernel VMA 内存管理：红黑树（按地址排序）
• Nginx timer：红黑树（按到期时间排序）
• epoll 内部事件管理：红黑树

10.3 B 树查找

B 树（Bayer-McCreight 1972）专为磁盘存储设计：每节点最多 $2t-1$ 个关键字、$2t$ 个子节点，根到叶等长（完美平衡）。

class BTreeNode:
    def __init__(self, t: int, leaf: bool = False):
        self.t = t  # 最小度数
        self.keys = []
        self.children = []
        self.leaf = leaf

def b_tree_search(node: BTreeNode, key):
    """B 树查找：O(log_t n)"""
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    if i < len(node.keys) and key == node.keys[i]:
        return (node, i)
    if node.leaf:
        return None
    return b_tree_search(node.children[i], key)

复杂度：$O(\log_t n)$，其中 $t$ 是最小度数。$t$ 越大，树高越低，磁盘 IO 越少。

典型参数：

• MySQL InnoDB：$t = 250$（16KB 页 / 64 字节每行 ≈ 250），10 亿行数据树高仅 3-4；
• PostgreSQL：8KB 页，类似参数；
• SQLite：4KB 页。

10.4 B+ 树（数据库索引的王者）

B+ 树是 B 树变体：

• 所有数据仅存于叶节点；
• 内部节点仅存索引关键字；
• 叶节点用双向链表连接。

优势：

• 内部节点不含数据，可容纳更多关键字，树高更低；
• 范围查询：从叶节点链表头部顺序扫描即可，$O(\log_t n + k)$；
• 所有关系数据库（MySQL、PostgreSQL、Oracle、SQL Server）的索引均采用 B+ 树。

10.5 Trie 树查找

Trie（Retrieval Tree，前缀树）按字符分解键，适合字符串前缀匹配：

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    
    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end
    
    def starts_with(self, prefix: str) -> bool:
        """前缀查找：Trie 的核心优势"""
        return self._find(prefix) is not None
    
    def _find(self, s: str):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

复杂度：$O(L)$，$L$ 为键长，与数据规模无关。

应用：自动补全、拼写检查、IP 路由（Longest Prefix Match）、DNS 解析。

11. 跳表查找

11.1 核心思想

跳表（Skip List, Pugh 1990）通过在有序链表上随机添加多层索引，实现 $O(\log n)$ 期望查找：

Level 3:  HEAD ------------------------------> 50 --------------------------> NIL
Level 2:  HEAD ---------> 20 ----------------> 50 --------------> 80 ------> NIL
Level 1:  HEAD ---> 10 --> 20 ---> 30 --------> 50 ---> 70 -----> 80 ---> 90 > NIL
Level 0:  HEAD > 5 > 10 > 20 > 25 > 30 > 40 > 50 > 60 > 70 > 75 > 80 > 85 > 90 > NIL

查找 70 的路径：从 Level 3 开始，50 < 70 下降到 Level 2，50 < 70 下降到 Level 1，80 > 70 下降到 Level 0，找到 70。共 $O(\log n)$ 次比较。

11.2 实现

import random

class SkipListNode:
    def __init__(self, key=None, level=0):
        self.key = key
        self.forward = [None] * level  # 各层的下一个节点

class SkipList:
    """跳表：期望 O(log n) 查找/插入/删除"""
    
    MAX_LEVEL = 16
    P = 0.5  # 上一层的概率
    
    def __init__(self):
        self.header = SkipListNode(level=self.MAX_LEVEL)
        self.level = 0  # 当前最高层
    
    def _random_level(self) -> int:
        """生成随机层高：几何分布"""
        lvl = 1
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl
    
    def search(self, key) -> bool:
        """查找：从最高层开始，遇大则下降"""
        node = self.header
        for i in range(self.level - 1, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
        node = node.forward[0]
        return node is not None and node.key == key
    
    def insert(self, key) -> None:
        """插入：随机层高 + 多层索引更新"""
        update = [None] * self.MAX_LEVEL
        node = self.header
        for i in range(self.level - 1, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
            update[i] = node
        
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level, lvl):
                update[i] = self.header
            self.level = lvl
        
        new_node = SkipListNode(key, lvl)
        for i in range(lvl):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
    
    def delete(self, key) -> bool:
        update = [None] * self.MAX_LEVEL
        node = self.header
        for i in range(self.level - 1, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
            update[i] = node
        target = node.forward[0]
        if target is None or target.key != key:
            return False
        for i in range(self.level):
            if update[i].forward[i] is not target:
                break
            update[i].forward[i] = target.forward[i]
        while self.level > 1 and self.header.forward[self.level - 1] is None:
            self.level -= 1
        return True