Searching Algorithms: Analysis & Applications

Efficiency comparison

Algorithm	Time	Space	Scenario
Sequential	$O(n)$	$O(1)$	Unordered/small
Block	$O(\sqrt{n})$	$O(\sqrt{n})$	Large table, frequent
Binary	$O(\log_2 n)$	$O(1)$	Sorted list
Hash	$O(1)$ (amort.)	$O(n)$	Very frequent / big data
B/B+ Tree	$O(\log_m n)$	$O(n)$	Disk/DB index
String matching	$O(m+n)$ (KMP)	$O(n)$	Text/sequence

查找算法效率对比演示

此处可扩展为查找算法效率、空间复杂度等可视化对比图表。

• 顺序查找：O(n)
• 分块查找：O(√n)
• 折半查找：O(log₂ n)
• 哈希表查找：O(1)
• B树/B+树查找：O(logₘ n)
• 字符串匹配（KMP）：O(m+n)

Space & difficulty

• Sequential/Binary: simple, tiny space
• Hash/B-Tree: extra structures, higher space, more complex

Scenario mapping

• Small, unordered: sequential
• Large, frequent lookups: hash, B/B+
• Sorted list: binary
• Range queries: B+
• Strings/sequences: KMP, etc.

Exercises

Exercise 1

Compare sequential, binary, and hash search (time + scenarios).

参考答案

思路：对比效率与应用。

步骤：

1. 顺序 $O(n)$，无序/小数据
2. 折半 $O(\log_2 n)$，有序表
3. 哈希 $O(1)$，大数据/高频

答案：小表顺序，有序折半，大数据哈希。

Exercise 2

需要频繁查找和区间查询，用什么结构？理由？

参考答案

思路：区间 + 高频 => B+。

步骤：

1. 频繁查找 + 区间，B+树最佳
2. 叶子链表便于范围

答案：B+树。

Past exam

2021·408

分析哈希 vs B-Tree on big data。

参考答案

思路：等值查 vs 范围查；空间 vs 磁盘友好。

步骤：

1. 哈希快、等值佳、空间大，不擅范围
2. B 树略慢，磁盘友好，支持范围

答案：哈希快但不适合范围；B 树适合磁盘与区间查询。

PreviousString Pattern MatchingString matching basics, classic algorithms, complexity, and practice.