第11章 查找算法
11.1 查找的基本概念
11.1.1 查找表与关键字
查找表是由同一类型元素（或记录）构成的集合，用于支持数据的查询操作。每个元素中用于标识自身的唯一值称为关键字（Key），查找操作即根据给定关键字在查找表中定位对应元素。
查找成功：找到与关键字匹配的元素，返回其位置或相关信息；
查找失败：未找到匹配元素，返回特定标识（如-1或null）。
11.1.2 平均查找长度（ASL）
衡量查找算法效率的核心指标是平均查找长度（Average Search Length, ASL），定义为查找过程中关键字比较次数的数学期望：
ASL=∑i=1nPi⋅Ci ASL = sum_{i=1}^{n} P_i cdot C_i ASL=i=1∑n​Pi​⋅Ci​
其中：
nnn为查找表中元素个数；
PiP_iPi​为查找第iii个元素的概率（通常假设等概率分布，即Pi=1/nP_i = 1/nPi​=1/n）；
CiC_iCi​为找到第iii个元素所需的关键字比较次数。
11.1.3 查找算法分类
根据查找表在操作过程中的动态特性，可分为：
静态查找：查找表仅支持查询操作，元素不增删（如顺序查找、二分查找）；
动态查找：查找表支持查询、插入、删除等操作（如哈希查找）。
11.2 顺序查找
11.2.1 算法原理
顺序查找（Sequential Search）是最基本的查找方法，对查找表的结构无要求（有序或无序均可）。其核心思想是从表的一端开始，逐个遍历元素并比较关键字，直至找到目标或遍历结束。
11.2.2 算法实现
以无序数组（查找表）为例，顺序查找的基本实现如下：
基础版本
python

	def sequential_search(arr, key): 
	"""顺序查找基础实现""" 
	for i in range(len(arr)): 
	if arr[i] == key: # 关键字匹配 
	return i # 查找成功，返回索引 
	return -1 # 查找失败

优化：哨兵机制
基础版本中，每次循环需判断“是否越界”（i < len(arr)）和“是否匹配”（arr[i] == key）两个条件。通过在数组末尾添加哨兵（目标关键字），可省去越界判断，优化效率：
python

	def sequential_search_sentinel(arr, key): 
	"""带哨兵的顺序查找""" 
	arr.append(key) # 末尾添加哨兵 
	i = 0 
	while arr[i] != key: # 仅需判断关键字匹配 
	i += 1 
	arr.pop() # 恢复原数组 
	# 若i等于原数组长度，说明遍历至哨兵，查找失败 
	return i if i < len(arr) else -1

11.2.3 性能分析

时间复杂度：
最坏情况：需遍历所有元素，比较次数为nnn，时间复杂度O(n)O(n)O(n)；
平均查找长度（等概率分布）：
ASL成功=1+2+⋯+nn=n+12 ASL_{ ext{成功}} = rac{1+2+cdots+n}{n} = rac{n+1}{2} ASL成功​=n1+2+⋯+n​=2n+1​
查找失败时，比较次数为n+1n+1n+1（含哨兵）。


空间复杂度：O(1)O(1)O(1)，无需额外空间。

11.2.4 适用场景
顺序查找适用于以下场景：
数据量较小（如n≤100n leq 100n≤100），简单直观；
查找表为无序结构（如未排序的数组或链表）；
存储结构不支持随机访问（如链表，无法通过索引直接定位元素）。
11.3 二分查找
11.3.1 算法原理
二分查找（Binary Search）又称折半查找，要求查找表必须是有序的顺序表（如升序数组）。其核心思想是利用数据有序性，通过折半缩小查找范围，每次排除一半元素，直至找到目标或范围为空。
11.3.2 算法步骤（升序数组）
1.初始化左边界low=0low = 0low=0，右边界high=n−1high = n-1high=n−1（nnn为数组长度）；
2.计算中间位置mid=⌊(low+high)/2⌋mid = lfloor (low + high)/2 floormid=⌊(low+high)/2⌋，比较arr[mid]arr[mid]arr[mid]与目标关键字keykeykey：
o若arr[mid]=keyarr[mid] = keyarr[mid]=key：查找成功，返回midmidmid；
o若arr[mid]>keyarr[mid] > keyarr[mid]>key：目标在左半区，更新high=mid−1high = mid - 1high=mid−1；
o若arr[mid]<keyarr[mid] < keyarr[mid]<key：目标在右半区，更新low=mid+1low = mid + 1low=mid+1；
3.重复步骤2，直至low>highlow > highlow>high（查找失败，返回−1-1−1）。
11.3.3 算法实现
非递归版本
python

	def binary_search(arr, key): 
	"""二分查找非递归实现（升序数组）""" 
	low, high = 0, len(arr)-1 
	while low <= high: # 循环条件：范围不为空 
	mid = (low + high) // 2 
	if arr[mid] == key: 
	return mid 
	elif arr[mid] > key: 
	high = mid - 1 # 缩小至左半区 
	else: 
	low = mid + 1 # 缩小至右半区 
	return -1 # 查找失败

递归版本
python

	def binary_search_recursive(arr, key, low, high): 
	"""二分查找递归实现""" 
	if low > high: 
	return -1 # 范围为空，查找失败 
	mid = (low + high) // 2 
	if arr[mid] == key: 
	return mid 
	elif arr[mid] > key: 
	return binary_search_recursive(arr, key, low, mid-1) # 递归左半区 
	else: 
	return binary_search_recursive(arr, key, mid+1, high) # 递归右半区

11.3.4 性能分析

时间复杂度：
每次查找范围缩小一半，最坏情况下需log⁡2n+1log_2 n + 1log2​n+1次比较（如n=1024n=1024n=1024时，最多比较11次），时间复杂度O(log⁡n)O(log n)O(logn)；
平均查找长度（等概率分布）：
ASL成功≈log⁡2(n+1)−1 ASL_{ ext{成功}} pprox log_2(n+1) - 1 ASL成功​≈log2​(n+1)−1

空间复杂度：
非递归版本：O(1)O(1)O(1)；
递归版本：O(log⁡n)O(log n)O(logn)（递归栈深度为log⁡nlog nlogn）。

11.3.5 注意事项
有序性要求：必须是有序表，且需支持随机访问（数组适用，链表不适用，因无法快速定位midmidmid）；
边界控制：更新lowlowlow和highhighhigh时需使用mid±1mid pm 1mid±1，避免死循环（如low=highlow = highlow=high时仍需判断）；
重复元素处理：若存在多个相同关键字，返回“其中一个”位置（非首个或最后一个），需额外逻辑（如查找首个出现位置时，需在arr[mid]=keyarr[mid] = keyarr[mid]=key时继续向左半区查找）。
11.3.6 适用场景
二分查找适用于大规模有序静态数据（如已排序的数组），尤其适合查询频繁、更新极少的场景（如字典检索、数据库静态索引）。
11.4 分块查找
11.4.1 算法原理
分块查找（Block Search）又称索引顺序查找，结合了顺序查找和二分查找的优点，适用于分块有序的查找表——即表中元素分成若干块，块内元素无序，但块间元素有序（如块1所有元素<块2所有元素<块3所有元素）。
分块查找需两个核心结构：
索引表：记录每块的“最大关键字”和“块起始地址”（块间有序）；
数据块：原始数据分成的若干子块，块内无序。
11.4.2 算法步骤
1.索引查找：在索引表中确定目标关键字所在的块（因块间有序，可采用二分查找或顺序查找）；
2.块内查找：在确定的块内采用顺序查找目标元素。
11.4.3 算法示例
设查找表为[8,3,12,6,15,21,18,24,20][8,3,12,6,15,21,18,24,20][8,3,12,6,15,21,18,24,20]，分3块（块大小s=3s=3s=3），索引表和数据块结构如下：

查找关键字18：
1.索引查找：18 < 21（块2最大关键字）→ 排除块1、块2；18 < 24（块3最大关键字）→ 确定块3（起始地址6）；
2.块内查找：在块3 [18,24,20][18,24,20][18,24,20]中顺序查找，找到18，位置6。
11.4.4 性能分析
设查找表总长度为nnn，分成bbb块，每块大小为sss（n=b×sn = b imes sn=b×s）：

若索引表采用二分查找（时间复杂度O(log⁡b)O(log b)O(logb)），块内采用顺序查找（时间复杂度O(s)O(s)O(s)），则总平均查找长度：
ASL=log⁡2(b+1)−1+s+12 ASL = log_2(b+1) - 1 + rac{s+1}{2} ASL=log2​(b+1)−1+2s+1​

最优块大小：当s=ns = sqrt{n}s=n​时，ASLASLASL最小，约为2n2sqrt{n}2n​，时间复杂度O(n)O(sqrt{n})O(n​)。

11.4.5 适用场景
分块查找适用于数据量大且分块有序的场景，如数据库分表存储、磁盘文件索引等。其优势在于：块内元素增删无需调整其他块，动态维护成本低于全局有序表。
11.5 哈希查找
11.5.1 核心概念
哈希查找（Hash Search）通过哈希函数将关键字直接映射为元素的存储地址，实现“关键字→地址”的快速定位。其核心挑战是处理冲突（不同关键字映射到同一地址）。
哈希表（Hash Table）：存储元素的数组，每个位置称为“桶”（Bucket）；
哈希函数：h(key)h(key)h(key)，将关键字映射为哈希表索引（桶地址）；
冲突：h(key1)=h(key2)h(key_1) = h(key_2)h(key1​)=h(key2​)且key1≠key2key_1 eq key_2key1​=key2​。
11.5.2 哈希函数的构造

1. 除留余数法（最常用）
   取关键字除以哈希表长度mmm的余数为哈希地址：
   h(key)=keymod  m h(key) = key mod m h(key)=keymodm
   注意：mmm宜取质数（如31、61、127），可减少冲突（若mmm为合数，可能导致关键字分布集中）。
2. 直接定址法
   取关键字或其线性函数为哈希地址：
   h(key)=key或h(key)=a⋅key+b h(key) = key quad ext{或} quad h(key) = a cdot key + b h(key)=key或h(key)=a⋅key+b
   （a,ba,ba,b为常数），适用于关键字分布连续的场景（如学号、身份证号）。
   11.5.3 冲突处理方法
3. 链地址法（拉链法）
   将哈希地址相同的元素链接成单链表，哈希表每个桶存储链表头指针。冲突时，新元素直接插入对应链表。
   示例：哈希函数h(key)=keymod  5h(key) = key mod 5h(key)=keymod5，关键字[12,22,32,42][12, 22, 32, 42][12,22,32,42]的哈希地址均为2，链地址法存储如下：
   哈希表索引0：∅
   索引1：∅
   索引2：12 → 22 → 32 → 42（冲突元素链表）
   索引3：∅
   索引4：∅
   优点：处理简单，无聚集现象（一个冲突不会引发其他冲突），动态增删方便。
4. 开放定址法
   冲突时，从冲突地址开始，按某种规则在哈希表中寻找空桶：
   hi(key)=(h(key)+di)mod  m h_i(key) = (h(key) + d_i) mod m hi​(key)=(h(key)+di​)modm
   其中did_idi​为增量序列，常见有：
   线性探测：di=0,1,2,⋯ ,m−1d_i = 0,1,2,cdots,m-1di​=0,1,2,⋯,m−1（依次向后探测）；
   二次探测：di=0,±12,±22,⋯ ,±k2d_i = 0,pm1^2,pm22,cdots,pm k^2di​=0,±12,±22,⋯,±k2（避免线性探测的“聚集”问题）。
   11.5.4 算法实现（链地址法）
   python

	class HashTable: 
	def __init__(self, size=10): 
	self.size = size 
	self.table = [[] for _ in range(size)] # 桶存储链表 
	
	def hash_func(self, key): 
	"""哈希函数：除留余数法""" 
	return key % self.size 
	
	def insert(self, key): 
	"""插入元素""" 
	idx = self.hash_func(key) 
	self.table[idx].append(key) 
	
	def search(self, key): 
	"""查找元素，返回桶索引和链表位置""" 
	idx = self.hash_func(key) 
	for i, val in enumerate(self.table[idx]): 
	if val == key: 
	return (idx, i) # (桶索引, 链表位置) 
	return (-1, -1) # 查找失败

11.5.5 性能分析
哈希查找的性能取决于负载因子α=nmlpha = rac{n}{m}α=mn​（nnn为元素个数，mmm为哈希表长度）：
αlphaα越小（表越空），冲突越少，查找效率越高；
链地址法在α=1lpha = 1α=1时，平均查找长度约为1.5；
理想情况下（无冲突），时间复杂度O(1)O(1)O(1)；极端冲突时（所有元素映射到同一桶），退化为顺序查找，时间复杂度O(n)O(n)O(n)。
11.5.6 适用场景
哈希查找适用于大规模动态数据（如缓存系统、数据库哈希索引），尤其适合查询频繁、增删频繁的场景（如用户会话管理、高频访问数据存储）。
11.6 查找算法对比与总结
11.6.1 算法性能对比

11.6.2 算法选择建议
数据量小（n≤100n leq 100n≤100）或无序：优先顺序查找；
数据量大且有序静态：优先二分查找；
数据量大且分块有序：优先分块查找；
数据量大且动态（增删频繁）：优先哈希查找（链地址法处理冲突）。
11.6.3 核心结论
查找算法的设计需权衡时间效率“空间效率”和“实现复杂度”。顺序查找是基础，二分查找利用有序性优化，分块查找平衡动态与静态特性，哈希查找通过映射实现极致

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49272.html