第22章 搜索算法理论

学习目标

• 掌握搜索问题的形式化定义与下界分析
• 理解二分查找的正确性证明与变体算法
• 掌握插值搜索的概率分析
• 理解搜索问题的最优性条件
• 掌握搜索算法的选择策略

---

22.1 搜索问题的形式化定义

22.1.1 问题定义

定义 22.1（搜索问题） 给定元素集合 $S$ 和目标值 $x$，搜索问题要求确定 $x$ 是否在 $S$ 中，若在则返回其位置。

定义 22.2（静态搜索） 集合 $S$ 固定不变，仅进行查询操作。

定义 22.3（动态搜索） 集合 $S$ 支持插入、删除和查询操作。

22.1.2 搜索模型

定义 22.4（比较搜索模型） 仅通过比较操作确定元素关系的搜索模型。

定理 22.1（静态搜索下界） 在比较模型下，$n$ 个元素的静态搜索问题最坏情况需要 $\Omega(\log n)$ 次比较。

证明：搜索问题的决策树至少需要 $n+1$ 个叶节点（$n$ 个可能位置加上"不存在"）。决策树高度 $h$ 满足：

$$2^h \geq n + 1 \Rightarrow h \geq \log_2(n+1)$$

故最坏情况至少需要 $\lceil \log_2(n+1) \rceil$ 次比较。 ∎

定理 22.2（平均情况下界） 在均匀分布假设下，成功搜索的平均比较次数为 $\Omega(\log n)$。

证明：设决策树有 $n$ 个成功叶节点，深度分别为 $d_1, d_2, \ldots, d_n$。平均深度：

$$\bar{d} = \frac{1}{n}\sum_{i=1}^{n} d_i$$

由Kraft不等式，$\sum_{i=1}^{n} 2^{-d_i} \leq 1$。当所有 $d_i$ 相等时，$\bar{d}$ 最小：

$$n \cdot 2^{-\bar{d}} \leq 1 \Rightarrow \bar{d} \geq \log_2 n$$

∎

---

22.2 线性搜索

22.2.1 算法描述

算法 22.1（线性搜索）

Linear-Search(A, x):
    for i = 1 to n:
        if A[i] = x:
            return i
    return NOT_FOUND

22.2.2 复杂度分析

定理 22.3 线性搜索的时间复杂度：

• 最坏情况：$O(n)$
• 平均情况（成功）：$O(n)$
• 平均情况（失败）：$O(n)$

证明：

• 最坏情况：目标在末尾或不存在，需检查所有元素
• 平均成功：设目标在第 $i$ 个位置的概率为 $\frac{1}{n}$，期望比较次数：

$$E[C] = \sum_{i=1}^{n} \frac{i}{n} = \frac{n+1}{2} = O(n)$$

∎

22.2.3 优化：带哨兵的线性搜索

from typing import List, TypeVar, Optional

T = TypeVar('T')

def linear_search(arr: List[T], target: T) -> int:
    for i, item in enumerate(arr):
        if item == target:
            return i
    return -1

def linear_search_sentinel(arr: List[T], target: T) -> int:
    if not arr:
        return -1
    
    last = arr[-1]
    arr[-1] = target
    
    i = 0
    while arr[i] != target:
        i += 1
    
    arr[-1] = last
    
    if i < len(arr) - 1 or target == last:
        return i
    return -1

def linear_search_generic(arr: List[T], key: callable, target) -> int:
    for i, item in enumerate(arr):
        if key(item) == target:
            return i
    return -1

---

22.3 二分查找

22.3.1 算法描述

定义 22.5（有序数组搜索） 在有序数组中查找目标元素。

算法 22.2（二分查找）

Binary-Search(A, x):
    left = 1
    right = n
    while left ≤ right:
        mid = floor((left + right) / 2)
        if A[mid] = x:
            return mid
        else if A[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return NOT_FOUND

22.3.2 正确性证明

定理 22.4（二分查找正确性） 若目标 $x$ 在有序数组 $A$ 中，二分查找返回其位置；否则返回 NOT_FOUND。

证明：使用循环不变式：每次迭代前，若 $x$ 在 $A$ 中，则 $x \in A[\text{left}..\text{right}]$。

初始化：$\text{left} = 1$，$\text{right} = n$，$x \in A[1..n]$ 若存在。

保持：

• 若 $A[\text{mid}] = x$，返回正确
• 若 $A[\text{mid}] < x$，由数组有序，$x \in A[\text{mid}+1..\text{right}]$，更新 $\text{left} = \text{mid}+1$
• 若 $A[\text{mid}] > x$，$x \in A[\text{left}..\text{mid}-1]$，更新 $\text{right} = \text{mid}-1$

终止：当 $\text{left} > \text{right}$ 时，搜索区间为空，$x$ 不在数组中。 ∎

22.3.3 复杂度分析

定理 22.5 二分查找的时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$（迭代）或 $O(\log n)$（递归）。

证明：每次迭代将搜索区间减半。设初始区间大小为 $n$，经过 $k$ 次迭代后区间大小为 $\lceil n/2^k \rceil$。当 $\lceil n/2^k \rceil < 1$ 时终止：

$$k \geq \log_2 n$$

故迭代次数为 $O(\log n)$。 ∎

22.3.4 最优性

定理 22.6（二分查找最优性） 二分查找达到比较搜索的下界。

证明：由定理22.1，搜索下界为 $\lceil \log_2(n+1) \rceil$。二分查找最坏情况比较次数为 $\lceil \log_2(n+1) \rceil$，达到下界。 ∎

22.3.5 Python实现

from typing import List, TypeVar, Callable, Optional, Tuple

T = TypeVar('T')

def binary_search(arr: List[T], target: T) -> int:
    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

def binary_search_recursive(arr: List[T], target: T, left: int = 0, right: Optional[int] = None) -> int:
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

def binary_search_generic(arr: List[T], key: Callable[[T], any], target: any) -> int:
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        mid_key = key(arr[mid])
        
        if mid_key == target:
            return mid
        elif mid_key < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

class BinarySearch:
    def __init__(self, arr: List[T]):
        self.arr = arr
    
    def search(self, target: T) -> int:
        return binary_search(self.arr, target)
    
    def search_range(self, target: T) -> Tuple[int, int]:
        return (
            self.find_first(target),
            self.find_last(target)
        )
    
    def find_first(self, target: T) -> int:
        left, right = 0, len(self.arr) - 1
        result = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if self.arr[mid] >= target:
                if self.arr[mid] == target:
                    result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result
    
    def find_last(self, target: T) -> int:
        left, right = 0, len(self.arr) - 1
        result = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if self.arr[mid] <= target:
                if self.arr[mid] == target:
                    result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result
    
    def count_occurrences(self, target: T) -> int:
        first = self.find_first(target)
        if first == -1:
            return 0
        last = self.find_last(target)
        return last - first + 1

---

22.4 二分查找变体

22.4.1 查找插入位置

定义 22.6（下界） 对于有序数组 $A$ 和目标 $x$，下界是第一个大于等于 $x$ 的元素位置。

定义 22.7（上界） 上界是第一个大于 $x$ 的元素位置。

def lower_bound(arr: List[T], target: T) -> int:
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            right = mid
        else:
            left = mid + 1
    
    return left

def upper_bound(arr: List[T], target: T) -> int:
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
    
    return left

def find_insert_position(arr: List[T], target: T) -> int:
    return lower_bound(arr, target)

22.4.2 旋转数组搜索

定义 22.8（旋转有序数组） 旋转有序数组是将有序数组在某点旋转得到的数组。

定理 22.7 旋转有序数组中搜索的时间复杂度为 $O(\log n)$。

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

def find_rotation_point(arr: List[int]) -> int:
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] > arr[right]:
            left = mid + 1
        else:
            right = mid
    
    return left

22.4.3 搜索二维矩阵

def search_matrix(matrix: List[List[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        mid_val = matrix[mid // cols][mid % cols]
        
        if mid_val == target:
            return True
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

def search_matrix_sorted_rows(matrix: List[List[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False
    
    row, col = 0, len(matrix[0]) - 1
    
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1
    
    return False

---

22.5 插值搜索

22.5.1 算法描述

定义 22.9（插值搜索） 插值搜索根据目标值估计其在数组中的位置，使用线性插值公式。

算法 22.3（插值搜索）

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

22.5.2 复杂度分析

定理 22.8 在均匀分布假设下，插值搜索的平均时间复杂度为 $O(\log \log n)$。

证明：设数组元素均匀分布在 $[a, b]$ 区间。每次探测位置为：

$$\text{pos} \approx \frac{x - a}{b - a} \cdot n$$

若 $x$ 确实在位置 $k$，则探测误差约为 $O(\sqrt{n})$。经过 $O(\log \log n)$ 次迭代可收敛到正确位置。 ∎

定理 22.9 插值搜索的最坏情况时间复杂度为 $O(n)$。

证明：当数据分布极不均匀时（如 $A = [1, 2, 3, \ldots, n-1, n^{100}]$），搜索 $x = n^{100}$ 需要线性时间。 ∎

22.5.3 Python实现

def interpolation_search(arr: List[int], target: int) -> int:
    if not arr:
        return -1
    
    left, right = 0, len(arr) - 1
    
    while left <= right and arr[left] <= target <= arr[right]:
        if arr[left] == arr[right]:
            if arr[left] == target:
                return left
            return -1
        
        pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
        pos = max(left, min(pos, right))
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

def interpolation_search_recursive(arr: List[int], target: int, left: int = 0, right: Optional[int] = None) -> int:
    if right is None:
        right = len(arr) - 1
    
    if left > right or target < arr[left] or target > arr[right]:
        return -1
    
    if arr[left] == arr[right]:
        return left if arr[left] == target else -1
    
    pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
    pos = max(left, min(pos, right))
    
    if arr[pos] == target:
        return pos
    elif arr[pos] < target:
        return interpolation_search_recursive(arr, target, pos + 1, right)
    else:
        return interpolation_search_recursive(arr, target, left, pos - 1)

---

22.6 指数搜索

22.6.1 算法描述

定义 22.10（指数搜索） 指数搜索首先确定搜索范围，然后在该范围内进行二分查找。

算法 22.4（指数搜索）

Exponential-Search(A, x):
    if A[1] = x:
        return 1
    i = 1
    while i < n and A[i] < x:
        i = i * 2
    return Binary-Search(A[i/2..min(i, n)], x)

22.6.2 复杂度分析

定理 22.10 指数搜索的时间复杂度为 $O(\log k)$，其中 $k$ 是目标位置。

证明：确定范围需要 $O(\log k)$ 次比较。范围大小为 $O(k)$，二分查找需要 $O(\log k)$。总计 $O(\log k)$。 ∎

22.6.3 Python实现

def exponential_search(arr: List[int], target: int) -> int:
    if not arr:
        return -1
    
    if arr[0] == target:
        return 0
    
    n = len(arr)
    bound = 1
    
    while bound < n and arr[bound] < target:
        bound *= 2
    
    left = bound // 2
    right = min(bound, n - 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

---

22.7 跳表搜索

22.7.1 数据结构

定义 22.11（跳表） 跳表是一种随机化数据结构，通过多层索引实现 $O(\log n)$ 期望时间的搜索。

定理 22.11 跳表的期望高度为 $O(\log n)$，期望搜索时间为 $O(\log n)$。

证明：每个元素以概率 $p$ 晋升到上一层。期望层数：

$$E[H] = \log_{1/p} n = O(\log n)$$

搜索时，每层期望移动 $O(1/p)$ 步，共 $O(\log n)$ 层，总期望时间 $O(\log n)$。 ∎

22.7.2 Python实现

import random
from typing import List, TypeVar, Optional, Generic

T = TypeVar('T')

class SkipListNode(Generic[T]):
    def __init__(self, val: T, level: int):
        self.val = val
        self.forward: List[Optional['SkipListNode[T]']] = [None] * level

class SkipList(Generic[T]):
    def __init__(self, p: float = 0.5, max_level: int = 16):
        self.p = p
        self.max_level = max_level
        self.level = 1
        self.head = SkipListNode(None, max_level)
        self._size = 0
    
    def _random_level(self) -> int:
        level = 1
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level
    
    def search(self, target: T) -> bool:
        current = self.head
        
        for i in range(self.level - 1, -1, -1):
            while current.forward[i] and current.forward[i].val < target:
                current = current.forward[i]
        
        current = current.forward[0]
        return current is not None and current.val == target
    
    def insert(self, val: T) -> None:
        update = [None] * self.max_level
        current = self.head
        
        for i in range(self.level - 1, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
            update[i] = current
        
        new_level = self._random_level()
        
        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
            self.level = new_level
        
        new_node = SkipListNode(val, new_level)
        
        for i in range(new_level):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
        
        self._size += 1
    
    def delete(self, val: T) -> bool:
        update = [None] * self.max_level
        current = self.head
        
        for i in range(self.level - 1, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        if current is None or current.val != val:
            return False
        
        for i in range(self.level):
            if update[i].forward[i] != current:
                break
            update[i].forward[i] = current.forward[i]
        
        while self.level > 1 and self.head.forward[self.level - 1] is None:
            self.level -= 1
        
        self._size -= 1
        return True
    
    def __len__(self) -> int:
        return self._size
    
    def __contains__(self, val: T) -> bool:
        return self.search(val)

---

22.8 算法比较

22.8.1 复杂度对比

算法	最坏情况	平均情况	适用条件
线性搜索	$O(n)$	$O(n)$	无序数组
二分查找	$O(\log n)$	$O(\log n)$	有序数组
插值搜索	$O(n)$	$O(\log \log n)$	均匀分布
指数搜索	$O(\log n)$	$O(\log k)$	无界数组
跳表搜索	$O(n)$	$O(\log n)$	动态集合

22.8.2 选择策略

场景	推荐算法	原因
小规模数据	线性搜索	常数因子小
有序静态数组	二分查找	最优
均匀分布数据	插值搜索	平均更快
无界/无限数组	指数搜索	适应性强
动态集合	跳表/平衡树	支持更新

---

22.9 本章小结

本章系统介绍了搜索算法：

1. 下界理论：比较搜索的 $\Omega(\log n)$ 下界
2. 线性搜索：$O(n)$，适用于无序数据
3. 二分查找：$O(\log n)$，达到下界，适用于有序数据
4. 插值搜索：$O(\log \log n)$ 平均，适用于均匀分布
5. 跳表：$O(\log n)$ 期望，支持动态操作

---

参考文献

1. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
2. Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.
3. Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.
4. Peterson, W. W. (1957). Addressing for random-access storage. IBM Journal of Research and Development, 1(2), 130-146.

---

下一章：第23章 高级搜索技术