5种查找方法之二分查找与哈希查找的区别（Python含图解）
> 本文整理 二分查找与哈希查找的区别，配合 Python 可运行代码与图解思路，对应数据结构第 7 章「查找」，适合期末复习和课程设计。
本章要点
查找是数据结构高频考点。常见 5 种查找方法：顺序查找、分块查找、二分查找、哈希查找、插值查找。本文重点讲后两种——二分查找和哈希查找的区别与代码实现。
– 二分查找：数据必须有序，时间复杂度 O(log n)，空间 O(1)
– 哈希查找：不要求有序，平均 O(1)，需要额外哈希表空间
– 怎么选：静态有序表用二分；频繁按键查询、可接受内存开销用哈希
5 种查找方法一览
| 方法 | 前提条件 | 时间复杂度 | 空间 |
|———-|————–|————–|——–|
| 顺序查找 | 无 | O(n) | O(1) |
| 分块查找 | 分块有序 | O(√n) | O(1) |
| 二分查找 | 全局有序 | O(log n) | O(1) |
| 哈希查找 | 哈希函数 | 平均 O(1) | O(n) |
| 插值查找 | 有序且均匀 | O(log log n) | O(1) |
期末试卷常问：二分查找和哈希查找的区别？ 记住上表四行对比即可。
二分查找（含图解思路）
有序数组 index: 0 1 2 3 4
数值: 10 20 30 40 50 查找 target=30
第1轮: lo=0, hi=4, mid=2 → a[2]=30 命中
最多比较 log₂(n) 次。前提：数组有序。
def binary_search(arr: list[int], target: int) -> int:
"""二分查找：有序数组，返回下标，不存在返回 -1"""
lo, hi = 0, len(arr) – 1
while lo <= hi:
mid = lo + (hi – lo) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid – 1
return -1
哈希查找（含图解思路）
键 21 → hash(21) % 表长 → 桶下标 5 → 直接取值（平均 O(1)）
Python 用 dict 即可，底层已实现哈希表：
def hash_search(table: dict[int, str], key: int) -> str | None:
return table.get(key)
完整对比 Demo
from typing import Any
def binary_search(arr: list[int], target: int) -> int:
lo, hi = 0, len(arr) – 1
while lo <= hi:
mid = lo + (hi – lo) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid – 1
return -1
def build_hash_table(keys: list[int], values: list[Any]) -> dict[int, Any]:
return dict(zip(keys, values))
def demo() -> None:
data = sorted([3, 7, 12, 18, 21, 25, 30, 33, 40])
labels = [f"学生{v}" for v in data]
table = build_hash_table(data, labels)
for target in [21, 19]:
idx = binary_search(data, target)
hv = table.get(target)
print(f"查找 {target}: 二分下标={idx}, 哈希结果={hv}")
if __name__ == "__main__":
demo()
运行输出：
查找 21: 二分下标=4, 哈希结果=学生21
查找 19: 二分下标=-1, 哈希结果=None
性能小实验
import random
import time
SIZE = 200_000
arr = sorted(random.randint(0, SIZE * 10) for _ in range(SIZE))
table = {x: x for x in arr}
targets = random.sample(arr, 1000)
t0 = time.perf_counter()
for t in targets:
binary_search(arr, t)
t_binary = time.perf_counter() – t0
t0 = time.perf_counter()
for t in targets:
table[t]
t_hash = time.perf_counter() – t0
print(f"1000次查询: 二分 {t_binary:.4f}s, 哈希 {t_hash:.4f}s")
数据量大、查询频繁时哈希更快；二分不占额外内存。
二分查找 vs 哈希查找：区别总结
| 对比项 | 二分查找 | 哈希查找 |
|————–|——————–|———————-|
| 数据是否有序 | 必须有序 | 不要求 |
| 时间复杂度 | O(log n) | 平均 O(1) |
| 空间复杂度 | O(1) | O(n) |
| 典型场景 | 有序成绩表查学号 | URL 去重、缓存键查询 |
| 实现难度 | 注意边界条件 | 语言内置 dict 即可 |
常见坑
1. 二分 while lo <= hi：漏写等号会漏掉最后一个元素
2. 二分 mid 计算：lo + (hi – lo) // 2 防溢出（Java/C++）
3. 哈希冲突：Python dict 已处理；手写哈希表需链地址法
4. 顺序查找混淆：无序小数组（n<20）顺序查找更简单，不必强行二分
课程设计怎么选
– 成绩表按学号排序，偶尔查单个学生 → 二分查找
– 爬虫收集 URL 去重、统计词频 → 哈希查找（set/dict）
– 数据量小、只查几次 → 顺序查找 足够
小结
记住一句话：有序用二分，高频键值用哈希。配合上面 Python 代码跑通 demo，期末「查找」大题就不慌。
有问题评论区贴题目，我帮你看该用哪种查找方法。
