第15章 查找算法
15.1 引言
在数据处理中，查找是指从一组数据（查找表）中找出关键字满足特定条件的元素的过程。无论是日常使用的通讯录查询、数据库中的记录检索，还是搜索引擎的关键词匹配，查找操作的效率都直接影响系统的响应速度。例如，在包含百万条记录的数据库中，若采用低效的查找方法，可能导致查询耗时长达数秒甚至分钟级，而高效查找算法可将时间缩短至毫秒级。
15.1.1 查找的基本概念
查找表：由同一类型元素（记录）组成的集合，每个元素包含关键字（用于唯一标识元素的属性，如学生的学号、商品的ID）和数据项（其他描述信息，如姓名、价格）。
查找成功：找到关键字等于给定值vb.net教程C#教程python教程SQL教程access 2010教程的元素，返回该元素的位置或数据项；
查找失败：未找到关键字等于给定值的元素，返回特定标识（如-1或None）。
15.1.2 查找算法的评价指标
衡量查找算法性能的核心指标是平均查找长度（Average Search Length, ASL），即查找过程中关键字比较次数的期望值，计算公式为：
ASL=∑i=1nPiCi ASL = sum_{i=1}^{n} P_i C_i ASL=i=1∑n​Pi​Ci​
其中：
n n n 为查找表中元素个数；
Pi P_i Pi​ 为查找第 i i i 个元素的概率（实际应用中常假设等概率查找，即 Pi=1/n P_i = 1/n Pi​=1/n）；
Ci C_i Ci​ 为找到第 i i i 个元素所需的关键字比较次数。
其他重要指标包括：
时间复杂度：算法执行时间与数据规模 n n n 的关系，反映算法的效率上限；
空间复杂度：算法执行过程中额外占用的存储空间；
动态适应性：对查找表中元素插入、删除操作的支持能力；
数据依赖性：对查找表的存储结构（如数组、链表）、数据有序性的要求。
15.2 线性查找
线性查找是最简单的查找方法，其核心是通过逐个比较元素的关键字实现查找，对数据是否有序无要求，适合处理小规模或无序数据。
15.2.1 顺序查找

1. 算法流程
   顺序查找（Sequential Search）从查找表的一端开始，依次将每个元素的关键字与目标值比较，直至找到目标元素或遍历完所有元素。具体步骤如下：
   1.初始化指针 i=0 i = 0 i=0（从表头开始）；
   2.比较 i i i 位置元素的关键字与目标值：
   o若相等，查找成功，返回当前位置 i i i；
   o若不等，指针 i i i 后移（i=i+1 i = i + 1 i=i+1）；
   3.若 i i i 超出表长，查找失败，返回 -1。
2. 代码实现（无序数组）
   python

	def sequential_search(arr, target): 
	"""顺序查找：在无序数组arr中查找目标值target，返回索引（-1表示查找失败）""" 
	for i in range(len(arr)): 
	if arr[i] == target: # 关键字比较 
	return i 
	return -1 # 遍历结束未找到

3. 性能分析
   以包含 n n n 个元素的无序数组为例：

查找成功的ASL：等概率下，每个元素被查找的概率 Pi=1/n P_i = 1/n Pi​=1/n，找到第 i i i 个元素需比较 i i i 次（i i i 从1开始计数）。因此：
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=5 n=5 n=5 时，ASL成功=(1+2+3+4+5)/5=3 ASL_{ ext{成功}} = (1+2+3+4+5)/5 = 3 ASL成功​=(1+2+3+4+5)/5=3，即平均需比较3次。

查找失败的ASL：需遍历所有 n n n 个元素，比较次数为 n n n，故 ASL失败=n ASL_{ ext{失败}} = n ASL失败​=n。

时间复杂度：最好情况 O(1) O(1) O(1)（目标为第一个元素），最坏情况 O(n) O(n) O(n)（目标为最后一个元素或不存在），平均情况 O(n) O(n) O(n)。

空间复杂度：仅需常数级临时变量，O(1) O(1) O(1)。

4. 优化：哨兵查找
   顺序查找中，每次循环需判断“指针是否越界”（i<n i < n i<n）和“关键字是否匹配”（arr[i]target arr[i] == target arr[i]target）两个条件。哨兵查找通过在数组末尾添加“哨兵”（目标值），可省去越界判断，减少比较次数。具体实现如下：
   python

	def sentinel_search(arr, target): 
	"""哨兵查找：在数组末尾添加目标值作为哨兵，优化越界判断""" 
	n = len(arr) 
	# 复制原数组并添加哨兵（避免修改原数组） 
	arr_sentinel = arr.copy() 
	arr_sentinel.append(target) 
	i = 0 
	while arr_sentinel[i] != target: # 无需判断i < n，因哨兵必匹配 
	i += 1 
	return i if i < n else -1 # i < n：查找成功；i = n：查找失败

优化效果：对于大规模数据，哨兵查找可减少约 n n n 次越界判断（遍历过程中），实际运行效率比普通顺序查找提升10%~20%。
15.2.2 适用场景
顺序查找的优势是实现简单、对数据无有序性要求，但其时间复杂度为 O(n) O(n) O(n)，仅适用于以下场景：
小规模数据（如 n≤100 n leq 100 n≤100）；
无序数据（如随机生成的日志ID）；
链表存储结构（无法随机访问，只能顺序遍历）。
15.3 二分查找
二分查找（Binary Search）又称折半查找，是一种针对有序数据的高效查找算法。其核心思想是通过不断缩小查找区间（每次减半），将查找范围从 n n n 快速压缩至 1 1 1，时间复杂度可降至 O(log⁡n) O(log n) O(logn)。
15.3.1 算法原理
二分查找的前提是查找表为有序结构（以下以升序为例），且支持随机访问（如数组）。具体步骤如下：
1.初始化查找区间：左边界 low=0 low = 0 low=0，右边界 high=n−1 high = n - 1 high=n−1（闭区间 [low,high][low, high][low,high]）；
2.计算区间中点 mid=⌊(low+high)/2⌋ mid = lfloor (low + high) / 2 floor mid=⌊(low+high)/2⌋；
3.比较中点元素 arr[mid] arr[mid] arr[mid] 与目标值：
o若 arr[mid]target arr[mid] == target arr[mid]target，查找成功，返回 mid mid mid；
o若 arr[mid]>target arr[mid] > target arr[mid]>target，目标值在左半区间，更新 high=mid−1 high = mid - 1 high=mid−1；
o若 arr[mid]<target arr[mid] < target arr[mid]<target，目标值在右半区间，更新 low=mid+1 low = mid + 1 low=mid+1；
4.重复步骤2~3，直至 low>high low > high low>high（区间为空），查找失败，返回 -1。
15.3.2 代码实现

1. 迭代实现（闭区间）
   python

	def binary_search(arr, target): 
	"""二分查找（迭代版）：在升序数组arr中查找target，返回索引（-1表示失败）""" 
	low, high = 0, len(arr) - 1 # 初始化闭区间[low, high] 
	while low <= high: # 区间非空时循环 
	mid = low + (high - low) // 2 # 计算中点（避免溢出：等价于(low+high)//2） 
	if arr[mid] == target: 
	return mid # 查找成功 
	elif arr[mid] > target: 
	high = mid - 1 # 目标在左半区间，更新右边界 
	else: 
	low = mid + 1 # 目标在右半区间，更新左边界 
	return -1 # 区间为空，查找失败

关键细节：
中点计算：使用 mid=low+(high−low)//2 mid = low + (high - low) // 2 mid=low+(high−low)//2 而非 (low+high)//2 (low + high) // 2 (low+high)//2，可避免 low+high low + high low+high 溢出（如 low low low 和 high high high 均为大整数时）；
边界更新：若 arr[mid]>target arr[mid] > target arr[mid]>target，目标必在 [low,mid−1][low, mid-1][low,mid−1]（因 mid mid mid 位置已排除），故 high=mid−1 high = mid - 1 high=mid−1，反之 low=mid+1 low = mid + 1 low=mid+1。
2. 递归实现
python

	def binary_search_recursive(arr, target): 
	"""二分查找（递归版）""" 
	def _search(low, high): 
	if low > high: # 递归终止条件：区间为空 
	return -1 
	mid = low + (high - low) // 2 
	if arr[mid] == target: 
	return mid 
	elif arr[mid] > target: 
	return _search(low, mid - 1) # 递归左半区间 
	else: 
	return _search(mid + 1, high) # 递归右半区间 
	return _search(0, len(arr) - 1) # 初始区间[0, n-1]

15.3.3 性能分析
以包含 n n n 个元素的升序数组为例：

查找成功的ASL：二分查找过程可抽象为一棵二叉判定树（每个节点代表一次比较，左子树为“目标在左半区间”，右子树为“目标在右半区间”）。树的高度 h=⌈log⁡2(n+1)⌉ h = lceil log_2(n+1) ceil h=⌈log2​(n+1)⌉，等概率下，ASL约为 log⁡2(n+1)−1 log_2(n+1) - 1 log2​(n+1)−1。例如 n=7 n=7 n=7 时，判定树高度为3，ASL = (1×1 + 2×2 + 4×3)/7 = 17/7 ≈ 2.43，接近 log⁡2(7+1)−1=3−1=2 log_2(7+1) - 1 = 3 - 1 = 2 log2​(7+1)−1=3−1=2。

查找失败的ASL：等于判定树的叶节点深度，最坏情况下为 log⁡2(n+1) log_2(n+1) log2​(n+1)。

时间复杂度：每次循环将区间缩小一半，循环次数为判定树高度 O(log⁡n) O(log n) O(logn)，故时间复杂度为 O(log⁡n) O(log n) O(logn)。

空间复杂度：迭代版 O(1) O(1) O(1)，递归版 O(log⁡n) O(log n) O(logn)（递归栈深度为判定树高度）。

15.3.4 二分查找的工程变种
实际应用中，二分查找常需处理“查找特定条件元素”的场景，如查找第一个等于目标的元素、最后一个小于目标的元素等，需调整边界条件。

1. 查找第一个等于目标的元素
   普通二分查找可能返回多个相同元素中的任意一个，若需返回第一个匹配元素，需在找到目标后继续向左查找：
   python

	def binary_search_first(arr, target): 
	"""查找有序数组中第一个等于target的元素索引（不存在返回-1）""" 
	low, high = 0, len(arr) - 1 
	res = -1 # 记录结果 
	while low <= high: 
	mid = low + (high - low) // 2 
	if arr[mid] == target: 
	res = mid # 暂存当前位置，继续向左查找更前的匹配元素 
	high = mid - 1 
	elif arr[mid] > target: 
	high = mid - 1 
	else: 
	low = mid + 1 
	return res

2. 插值查找
   普通二分查找的中点 mid=(low+high)//2 mid = (low + high) // 2 mid=(low+high)//2 是固定的，未考虑目标值在区间中的分布。插值查找根据目标值与区间端点的比例动态计算中点：
   mid=low+target−arr[low]arr[high]−arr[low]×(high−low) mid = low + rac{target - arr[low]}{arr[high] - arr[low]} imes (high - low) mid=low+arr[high]−arr[low]target−arr[low]​×(high−low)
   当数据均匀分布时（如0~100的连续整数），插值查找的中点更接近目标值，ASL可优化至 O(log⁡log⁡n) O(log log n) O(loglogn)；但数据分布不均时（如指数增长序列），性能可能退化为 O(n) O(n) O(n)。
   15.3.5 适用场景
   二分查找适用于大规模有序静态数据（数据不频繁修改），例如：
   静态有序数组（如历史温度记录、字典单词表）；
   数据库中的索引字段（如主键索引，需提前排序）；
   工程中需频繁查询且数据稳定的场景（避免因插入/删除导致数组元素移动的开销）。
   15.4 树表查找
   树表查找是基于树结构的查找方法，通过将数据组织为有序树（如二叉搜索树、平衡树），实现动态数据的高效查找。与二分查找相比，树表查找支持高效的插入和删除操作，适合动态变化的数据集。
   15.4.1 二叉搜索树（BST）查找
3. 算法原理
   二叉搜索树（Binary Search Tree, BST）是一种满足以下性质的二叉树：
   左子树中所有节点的关键字均小于根节点的关键字；
   右子树中所有节点的关键字均大于根节点的关键字；
   左、右子树也为二叉搜索树。
   基于上述性质，BST查找过程如下：
   1.从根节点开始，比较当前节点的关键字与目标值；
   2.若相等，查找成功，返回当前节点；
   3.若目标值小于当前节点关键字，递归查找左子树；
   4.若目标值大于当前节点关键字，递归查找右子树；
   5.若当前节点为空（子树不存在），查找失败，返回 None。
4. 代码实现
   python

	class BSTNode: 
	"""二叉搜索树节点""" 
	def __init__(self, key): 
	self.key = key # 关键字 
	self.left = None # 左子树 
	self.right = None # 右子树 
	
	def bst_search(root, target): 
	"""在二叉搜索树root中查找目标值target，返回节点（None表示失败）""" 
	current = root 
	while current: 
	if current.key == target: # 关键字匹配 
	return current 
	elif target < current.key: # 目标在左子树 
	current = current.left 
	else: # 目标在右子树 
	current = current.right 
	return None # 查找失败

3. 性能分析
   BST的查找性能取决于树的高度：
   平衡BST：树高 h=O(log⁡n) h = O(log n) h=O(logn)，查找时间复杂度 O(log⁡n) O(log n) O(logn)，与二分查找相当；
   不平衡BST：若插入序列有序（如1,2,3,4），BST会退化为链表，树高 h=n h = n h=n，查找时间复杂度退化为 O(n) O(n) O(n)（与顺序查找相同）。
   为解决BST的不平衡问题，需引入平衡二叉搜索树。
   15.4.2 平衡树查找
   平衡树通过旋转或变色操作维持树高为 O(log⁡n) O(log n) O(logn)，确保查找性能稳定。常见的平衡树包括AVL树和红黑树。
4. AVL树查找
   AVL树是最早的平衡树，要求任意节点的左右子树高度差（平衡因子）的绝对值 ≤ 1。通过左旋、右旋等旋转操作，AVL树可将树高严格控制在 log⁡ϕn log_{phi} n logϕ​n（ϕ phi ϕ 为黄金比例，约1.618），接近 log⁡2n log_2 n log2​n。其查找过程与BST相同，但因树高稳定，时间复杂度始终为 O(log⁡n) O(log n) O(logn)。
5. 红黑树查找
   红黑树通过以下规则维持“从根到叶的最长路径 ≤ 2×最短路径”：
   每个节点非红即黑；
   根节点为黑；
   红节点的子节点必为黑（无连续红节点）；
   从任一节点到其叶节点的所有路径包含相同数量的黑节点。
   红黑树的树高约为 2log⁡2(n+1) 2log_2(n+1) 2log2​(n+1)，查找时间复杂度为 O(log⁡n) O(log n) O(logn)。与AVL树相比，红黑树插入/删除时的旋转次数更少（平均1~2次），实际应用更广泛（如Java的TreeMap、C++的std::map底层实现）。
   15.4.3 适用场景
   树表查找适用于动态数据（频繁插入/删除），例如：
   数据库中的动态索引（如B+树，基于平衡树扩展，支持磁盘存储）；
   有序集合（如按关键字范围查询“所有成绩在80~90分的学生”）；
   内存中的中小规模数据（大规模数据需结合磁盘分页机制）。
   15.5 哈希查找
   哈希查找（Hash Search）基于哈希表（Hash Table）实现，通过哈希函数将关键字直接映射到存储地址，实现“关键字→地址”的快速访问，平均查找时间复杂度接近 O(1) O(1) O(1)，是工程中高效查找的首选方案。
   15.5.1 基本原理
   哈希查找的核心是哈希函数和冲突处理：
   哈希函数：将关键字 key key key 映射到哈希表的索引 idx idx idx，记为 idx=H(key) idx = H(key) idx=H(key)。理想情况下，不同关键字映射到不同索引（无冲突）；
   冲突：多个关键字映射到同一索引的现象（因关键字集合通常大于哈希表容量）；
   冲突处理：解决冲突的方法，常用的有链地址法、开放定址法等。
   15.5.2 链地址法哈希查找
   链地址法是最常用的冲突处理方法：哈希表的每个索引（桶）对应一个链表，冲突的关键字按序存入链表。查找时，先通过哈希函数定位桶，再遍历链表比较关键字。
6. 哈希表结构与查找流程
   哈希表由数组（桶数组）和链表（冲突链）组成，查找流程如下：
   1.计算目标关键字的哈希索引 idx=H(key) idx = H(key) idx=H(key)；
   2.遍历 idx idx idx 对应的链表，比较每个节点的关键字与目标值：
   o若匹配，查找成功，返回节点数据；
   o若遍历完链表未匹配，查找失败。
7. 代码实现（链地址法）
   python

	class HashTable: 
	def __init__(self, capacity=16, load_factor=0.7): 
	"""初始化哈希表：capacity为桶数组容量，load_factor为装填因子阈值""" 
	self.capacity = capacity # 桶数组容量 
	self.load_factor = load_factor # 装填因子（元素数/容量）阈值，超过则扩容 
	self.size = 0 # 当前元素数 
	self.buckets = [[] for _ in range(capacity)] # 桶数组（每个桶为链表） 
	
	def _hash(self, key): 
	"""哈希函数：计算关键字key的哈希索引（简化版，实际需根据key类型设计）""" 
	return hash(key) % self.capacity # 除留余数法 
	
	def insert(self, key, value): 
	"""插入键值对(key, value)，若key已存在则更新value""" 
	idx = self._hash(key) 
	# 遍历桶链表，检查key是否已存在 
	for i, (k, v) in enumerate(self.buckets[idx]): 
	if k == key: 
	self.buckets[idx][i] = (key, value) # 更新value 
	return 
	# 插入新键值对到桶链表头部 
	self.buckets[idx].append((key, value)) 
	self.size += 1 
	# 若装填因子超过阈值，扩容（容量翻倍） 
	if self.size / self.capacity > self.load_factor: 
	self._resize(self.capacity * 2) 
	
	def search(self, key): 
	"""查找关键字key对应的值，不存在返回None""" 
	idx = self._hash(key) 
	# 遍历桶链表查找key 
	for k, v in self.buckets[idx]: 
	if k == key: 
	return v 
	return None # 未找到 
	
	def _resize(self, new_capacity): 
	"""扩容：创建新桶数组，重新哈希所有键值对""" 
	old_buckets = self.buckets 
	self.capacity = new_capacity 
	self.buckets = [[] for _ in range(new_capacity)] 
	self.size = 0 
	# 重新插入所有键值对 
	for bucket in old_buckets: 
	for key, value in bucket: 
	self.insert(key, value)

3. 性能分析
   哈希查找的性能主要取决于装填因子 α=元素数桶数组容量 lpha = rac{ ext{元素数}}{ ext{桶数组容量}} α=桶数组容量元素数​：
   α lpha α 越小，桶链表越短，查找效率越高。理想情况下（无冲突），查找时间复杂度为 O(1) O(1) O(1)；
   链地址法中，查找成功的ASL约为 1+α2 1 + rac{lpha}{2} 1+2α​，失败的ASL约为 e−α+α e^{-lpha} + lpha e−α+α（e e e 为自然常数）。
   当 α=0.7 lpha = 0.7 α=0.7（工程中常用阈值）时，平均查找长度约为1.35，接近 O(1) O(1) O(1)。
   15.5.3 适用场景
   哈希查找适用于频繁查找、关键字分布均匀的场景，例如：
   缓存系统（如Redis中的键值存储，通过哈希表实现O(1)查找）；
   数据库索引（如哈希索引，适合等值查询，不支持范围查询）；
   编译器的符号表（快速查找变量名对应的内存地址）。
   15.6 查找算法对比与选择
   15.6.1 算法性能对比

（注：m m m 为哈希表容量，n n n 为元素数）
15.6.2 工程选择策略
1.小规模数据（n<100 n < 100 n<100）：优先选择顺序查找，实现简单，无需预处理；
2.大规模静态有序数据：选择二分查找，空间效率高，ASL低（O(log⁡n) O(log n) O(logn)）；
3.动态数据（频繁插入/删除）：选择平衡树查找（如红黑树），兼顾有序性和动态性；
4.超高频查找（如缓存、索引）：选择哈希查找，平均 O(1) O(1) O(1) 时间，但需保证关键字分布均匀，避免冲突恶化性能。
15.7 本章总结
查找算法是数据处理的基础工具，其性能直接影响系统效率。本章系统介绍了四类核心查找算法，可总结为：
顺序查找：简单但低效，适合小规模或无序数据；
二分查找：基于有序数组，通过折半实现 O(log⁡n) O(log n) O(logn) 查找，适合静态有序数据；
树表查找：基于平衡树，支持动态数据和有序遍历，性能稳定为 O(log⁡n) O(log n) O(logn)；
哈希查找：通过哈希函数直接映射地址，平均 O(1) O(1) O(1) 查找，适合频繁查找、关键字分布均匀的场景。
工程实践中，需根据数据规模、动态性、有序性要求及查找频率综合选择算法，必要时结合多种方法（如数据库同时使用B+树索引和哈希索引）。
15.8 思考题
1.实现二分查找的变种：在有序数组中查找最后一个小于目标值的元素索引（如数组 [1,3,5,7,9]，目标值6，返回索引2）。
2.已知一个长度为 n n n 的有序数组在某个位置旋转（如 [0,1,2,4,5,6,7] 旋转后为 [4,5,6,7,0,1,2]），设计算法判断目标值是否存在，要求时间复杂度 O(log⁡n) O(log n) O(logn)。
3.对比链地址法和开放定址法（如线性探测）在哈希查找中的优缺点，分析在高装填因子（α>0.8 lpha > 0.8 α>0.8）下哪种方法更优。
4.用红黑树实现一个有序映射，支持按关键字范围查询（如“查找所有key在 [10, 50] 之间的键值对”）。
5.分析哈希查找中，哈希函数的设计对冲突率的影响，列举3种适合字符串关键字的哈希函数（如BKDRHash、APHash）并说明原理。

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