查找算法对比

各算法对比总表

详细分析

1. 顺序查找（Sequential Search）

int SeqSearch(ElemType A[], int n, KeyType key) {
    for (int i = 0; i < n; i++)
        if (A[i] == key) return i;
    return -1;
}

• 时间：$O(n)$
• ASL成功：(n+1)/2
• ASL失败：n
• 优点：实现简单，对数据无要求
• 缺点：效率低

带哨兵的顺序查找：

int SeqSearch2(ElemType A[], int n, KeyType key) {
    A[0] = key;  // 哨兵
    int i = n;
    while (A[i] != key) i--;
    return i;  // 返回 0 表示失败
}

ASL成功：(n+1)/2（不变），但减少了一次比较判断。

2. 折半查找（Binary Search）

int BinarySearch(ElemType A[], int n, KeyType key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (A[mid] == key) return mid;
        else if (A[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

• 时间：$O(\log n)$
• ASL成功：$\approx \log_2(n+1) - 1$
• ASL失败：$\approx \log_2(n+1)$
• 优点：效率高
• 缺点：要求有序 + 顺序存储（不支持链表）

3. 分块查找

详见 分块查找。

• 时间：$O(\sqrt n)$
• ASL：$\sqrt n + 1$（最优分块时）

4. 二叉搜索树（BST）

• ASL成功最好：$O(\log n)$（平衡时）
• ASL成功最坏：$O(n)$（退化为链表）
• ASL失败：$O(n)$

5. 平衡二叉树（AVL）

• ASL：$\approx 1.44\log_2n$
• 保证：最坏情况也是 $O(\log n)$

6. B 树

• m 阶 B 树：每个节点最多 m 棵子树
• 查找时间：$O(\log_m n)$
• 适用：磁盘等外部存储

7. 散列表（Hash Table）

• ASL成功：取决于装填因子 $\alpha$，约为 $1 + \alpha/2$（链地址法）
• ASL失败：约为 $1 + \alpha$（链地址法）
• 理想情况：$O(1)$
• 最坏情况：$O(n)$（所有元素冲突）