Python常用算法——查找算法
Python查找算法全面解析：从顺序查找到红黑树
引言
查找是计算机科学中最基础且最重要的操作之一。无论你是开发简单的脚本还是构建复杂的系统，都离不开查找操作。本文将全面解析Python中实现的各种查找算法，从最简单的顺序查找到高效的红黑树查找，带你深入理解每种算法的原理、实现和适用场景。
一、基本查找算法
1.1 顺序查找（线性查找）
顺序查找是最简单的查找方法，适用于无序或有序序列。
实现原理：从头到尾遍历序列，逐个比较元素直到找到目标。
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos + 1
return found
# 测试
list = [2, 3, 1, 4, 5, 6, 0]
print(sequentialSearch(list, 5)) # True
print(sequentialSearch(list, 7)) # False
时间复杂度：O(n)
适用场景：小规模数据、无序数据
1.2 有序表的顺序查找
当数据有序时，可以提前终止查找，提高效率。
def ordersequentialSearch(alist,item):
pos = 0
found = False
stop = False
while pos < len(alist) and not found and not stop:
if alist[pos] == item:
found = True
else:
if alist[pos] > item:
stop = True
else:
pos = pos + 1
return found
二、二分查找及其变种
2.1 经典二分查找
二分查找要求数据必须有序，通过不断缩小查找范围实现高效查找。
def binary_search(lis, key):
low = 0
high = len(lis) - 1
time = 0
while low < high:
time += 1
mid = int((low + high) / 2)
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else:
print("查找次数: %s" % time)
return mid
return False
时间复杂度：O(log n)
适用场景：有序数据的静态查找
2.2 递归实现二分查找
def binarySearchCur(alist,item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binarySearchCur(alist[:midpoint],item)
else:
return binarySearchCur(alist[midpoint+1:],item)
2.3 插值查找
插值查找是对二分查找的改进，根据关键字在有序表中的位置估计mid的值。
def binary_search(lis, key):
low = 0
high = len(lis) - 1
while low < high:
# 插值查找的核心：根据关键字分布自适应计算mid
mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else:
return mid
return False
适用场景：数据分布均匀的有序表，性能优于二分查找
2.4 斐波那契查找
斐波那契查找利用黄金分割原理，通过斐波那契数列确定分割点。
def fibonacciSearch(self, array, key):
fibonacci_list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
n = len(array)
for i in range(len(fibonacci_list)):
if fibonacci_list[i] >= n:
ind = i
break
# 补全数组
if fibonacci_list[ind] > n:
array.extend([array[-1]] * (fibonacci_list[ind] - n))
# 查找逻辑...
三、分块查找
分块查找是顺序查找和二分查找的折中方案，将数据分成若干块，块内无序但块间有序。
def div_group_func(list_data, long):
# 分组，计算每组的最小值作为索引
n = num_all // long
for i in range(n):
begin = long * i
ending = long * (i + 1) - 1
min_f = list_data[begin]
start.append(begin)
end.append(ending)
# 获取每组最小值
for j in range(1, long):
if (begin + j) < num_all:
if min_f > list_data[begin + j]:
min_f = list_data[begin + j]
key.append(min_f)
def search_func(list_data, search, long):
# 先在索引中查找所在块，再在块内顺序查找
for i in range(n):
if search >= key[i]:
for j in range(start[i], end[i] + 1):
if search == list_data[j]:
print('查找成功')
return
时间复杂度：O(log m + n/m)
适用场景：数据量大且需要快速插入的场景
四、哈希查找
哈希查找通过哈希函数将关键字映射到表中，实现近乎O(1)的查找效率。
4.1 除留余数法+线性探测
class HashTable:
def __init__(self,size):
self.elem = [None for i in range(size)]
self.count = size
def hash(self,key):
return key % self.count
def insert_hash(self,key):
address = self.hash(key)
# 线性探测解决冲突
while self.elem[address]:
address = (address + 1) % self.count
self.elem[address] = key
def search_hash(self,key):
star = address = self.hash(key)
while self.elem[address] != key:
address = (address + 1) % self.count
if not self.elem[address] or address == star:
return False
return True
时间复杂度：平均O(1)，最坏O(n)
适用场景：需要快速查找，内存充足的场景
五、二叉排序树查找
二叉排序树（BST）是一种动态查找结构，支持高效地插入和删除操作。
class BST:
def __init__(self, node_list):
self.root = Node(node_list[0])
for data in node_list[1:]:
self.insert(data)
def search(self, node, parent, data):
if node is None:
return False, node, parent
if node.data == data:
return True, node, parent
if node.data > data:
return self.search(node.lchild, node, data)
else:
return self.search(node.rchild, node, data)
def insert(self, data):
flag, n, p = self.search(self.root, self.root, data)
if not flag:
new_node = Node(data)
if data > p.data:
p.rchild = new_node
else:
p.lchild = new_node
时间复杂度：平均O(log n)，最坏O(n)
适用场景：动态数据，频繁插入删除
六、平衡二叉树（AVL树）
AVL树是高度平衡的二叉搜索树，任何节点的左右子树高度差不超过1。
class AVLTree:
# 左旋（LL型调整）
def singleLeftRotate(self, node):
k1 = node.left
node.left = k1.right
k1.right = node
node.height = max(self.height(node.right), self.height(node.left)) + 1
k1.height = max(self.height(k1.left), node.height) + 1
return k1
# 右旋（RR型调整）
def singleRightRotate(self, node):
k1 = node.right
node.right = k1.left
k1.left = node
node.height = max(self.height(node.right), self.height(node.left)) + 1
k1.height = max(self.height(k1.right), node.height) + 1
return k1
# 插入并保持平衡
def _insert(self, node, key):
# ...插入逻辑
# 检查平衡性并旋转
if (self.height(node.left) - self.height(node.right)) == 2:
if key < node.left.key:
node = self.singleLeftRotate(node) # LL型
else:
node = self.doubleLeftRotate(node) # LR型
七、红黑树
红黑树是一种自平衡二叉查找树，通过颜色约束保持大致平衡。
class RBTree:
def __init__(self):
self.nil = RBTreeNode(0) # 哨兵节点
self.root = self.nil
def leftRotate(self, x):
y = x.right
x.right = y.left
if y.left != self.nil:
y.left.parent = x
y.parent = x.parent
if x.parent == self.nil:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def rbInsert(self, z):
# 插入逻辑
y = self.nil
x = self.root
while x != self.nil:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
# ...插入后修复红黑性质
self.rbInsertFixup(z)
def rbInsertFixup(self, z):
# 修复红黑树性质
while z.parent.color == 'red':
# 根据叔叔节点颜色分情况处理
# ...旋转和变色操作
红黑树的性质：
- 每个节点是红色或黑色
- 根节点是黑色
- 叶子节点（NIL）是黑色
- 红色节点的子节点必须是黑色
- 任意节点到叶子节点的路径包含相同数量的黑色节点
八、性能对比
下面是各查找算法的时间复杂度对比：
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 顺序查找 | O(n) | O(n) | O(1) | 小规模数据 |
| 二分查找 | O(log n) | O(log n) | O(1) | 有序静态数据 |
| 插值查找 | O(log log n) | O(n) | O(1) | 均匀分布有序数据 |
| 分块查找 | O(log m + n/m) | O(n) | O(m) | 索引结构 |
| 哈希查找 | O(1) | O(n) | O(n) | 内存充足 |
| 二叉排序树 | O(log n) | O(n) | O(n) | 动态数据 |
| AVL树 | O(log n) | O(log n) | O(n) | 频繁查找 |
| 红黑树 | O(log n) | O(log n) | O(n) | 频繁插入删除 |
九、实战应用
学生信息管理系统中的查找
def binary_search(lst, uid):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high)//2
if lst[mid]["uid"] == uid:
return lst[mid]
elif lst[mid]["uid"] < uid:
low = mid + 1
else:
high = mid - 1
return None
# 生成测试数据
students = get_students(100000)
result = binary_search(students, 1005)
结语
查找算法是数据结构与算法的核心内容，选择合适的查找算法能显著提升程序性能。对于小规模数据，简单查找即可；对于有序静态数据，二分查找及其变种是不错的选择；对于动态数据，树形结构更为合适；而对于追求极致性能的场景，哈希表和红黑树则是不二之选。
理解每种算法的原理和适用场景，才能在面对实际问题时做出最优选择。希望本文能帮助你更好地掌握Python中的查找算法，在实际项目中游刃有余。
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
最新评论
A /
肖松 /
xx /