顺序查找和折半查找

一、顺序查找（Sequential Search）

算法

从表的一端开始，逐个比较关键字。

int SeqSearch(SSTable ST, KeyType key) {
    ST.elem[0].key = key;  // 哨兵
    int i = ST.length;
    while (ST.elem[i].key != key)
        i--;
    return i;  // 0表示查找失败
}

哨兵作用

• 避免每次循环检查 i >= 0
• 简化代码，提高效率

时间复杂度

• ASL（成功）：$(n+1)/2$
• ASL（失败）：$n+1$
• 时间复杂度：$O(n)$

适用场景

• 无序表
• 链表
• 小规模数据

二、折半查找（Binary Search）

前提条件

• 有序表
• 顺序存储（随机访问）

算法

int BinarySearch(SSTable ST, KeyType key) {
    int low = 1, high = ST.length;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (ST.elem[mid].key == key)
            return mid;
        else if (ST.elem[mid].key < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;  // 查找失败
}

判定树

折半查找过程可以用判定树表示：

• 每个结点是一次比较
• 左子树：小于中间值
• 右子树：大于中间值

n 个结点的判定树：

• 深度：$\lfloor \log_2 n \rfloor + 1$
• 是完全二叉树（或接近完全二叉树）

时间复杂度

• ASL（成功）：$\approx \log_2(n+1) - 1$
• 时间复杂度：$O(\log_2 n)$

ASL（Average Search Length）

$$ASL = \sum_{i=1}^{n} p_i \times c_i$$

• $p_i$：查找第 i 个元素的概率
• $c_i$：查找第 i 个元素的比较次数

折半查找 ASL 计算

$n=7$ 的判定树：

• 第 1 层：1 个结点，比较 1 次
• 第 2 层：2 个结点，比较 2 次
• 第 3 层：4 个结点，比较 3 次

$ASL = (1\times1 + 2\times2 + 4\times3) / 7 = \frac{17}{7} \approx 2.43$

一般公式

n 个结点的折半查找判定树：

• 深度 $h = \lfloor \log_2 n \rfloor + 1$
• ASL ≈ $\log_2(n+1) - 1$

1. 插值查找

根据关键字分布自适应调整 mid：

$$mid = low + \frac{key - ST[low]}{ST[high] - ST[low]} \times (high - low)$$

适用于均匀分布的数据。

2. 斐波那契查找

利用斐波那契数列分割区间：

• $mid = low + F[k-1] - 1$
• 适用场景类似插值查找

例 1：折半查找过程

有序表：1, 3, 5, 7, 9, 11, 13, 15，查找 $key = 13$。

比较 3 次，找到！

例 2：折半查找失败

有序表同上，查找 $key = 6$。

例 3：构造判定树

有序表：A, B, C, D, E, F, G, H, I（关键字 1–9）。

构造过程：

1. $mid = (1+9)/2 = 5$，根为 E
2. 左子树 [1,4]，$mid = (1+4)/2 = 2$，为 B
3. 右子树 [6,9]，$mid = (6+9)/2 = 7$，为 G
4. 递归……

           E(5)
         /     \
       B(2)     G(7)
      / \      / \
    A(1) C(3) F(6) H(8)
          \          \
          D(4)        I(9)