第6章 搜索算法
搜索是计算机科学中最基本的操作之一，它的目标是在数据集合中找到特定的元素或判断元素是否存在。搜索算法的性能直接影响程序的整体效率。本章将介绍多种搜索算法，从简单的线性搜索到高效的哈希表。
6.1 线性搜索
线性搜索是最直观的搜索方法，它从数据集合的第一个元素开始，依次检查每个元素，直到找到目标元素或遍历完整个集合。线性搜索适用于任何类型的数据集合，不需要数据有任何特殊的组织形式。
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
def linear_search_with_count(arr, target):
comparisons = 0
for i in range(len(arr)):
comparisons += 1
if arr[i] == target:
return i, comparisons
return -1, comparisons
data = [3, 7, 2, 9, 5, 1, 8, 4, 6]
target = 5
index, count = linear_search_with_count(data, target)
print(f"在位置{index}找到{target}, 比较次数: {count}")
线性搜索的时间复杂度为O(n)，在最坏情况下需要遍历所有n个元素。线性搜索的空间复杂度为O(1)，不需要额外的存储空间。线性搜索适用于小规模数据、无序数据以及只需要偶尔搜索的场景。
Linear Search Animation
虽然线性搜索效率不高，但它在某些场景下仍然有用。当数据规模很小，或者数据经常变化导致无法维护有序结构时，线性搜索是最简单可行的方案。线性搜索也可以用于查找满足特定条件的元素，而不只是精确匹配。
6.2 二分搜索
Binary Search Animation
二分搜索是一种高效的搜索算法，它利用数据的有序性，每次将搜索范围缩小一半。二分搜索要求数据集合必须有序，可以是升序或降序排列。算法从中间元素开始比较，如果目标元素小于中间元素，则在左半部分继续搜索；如果大于中间元素，则在右半部分继续搜索。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def binary_search_recursive(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
sorted_data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
index = binary_search(sorted_data, target)
print(f"在有序数组的位置{index}找到{target}")
二分搜索的时间复杂度为O(log n)，因为每次搜索范围缩小一半，最多需要log n次比较。空间复杂度在迭代版本中为O(1)，在递归版本中为O(log n)，因为需要递归栈空间。
二分搜索相比线性搜索有巨大的性能优势。在100万元素的数组中，线性搜索平均需要50万次比较，二分搜索最多只需要20次比较。二分搜索广泛应用于有序数组、字典查找、数据库索引等场景。
二分搜索还可以用于查找满足特定条件的位置。比如查找第一个大于目标元素的位置，或查找最后一个小于目标元素的位置。这些变种在实际应用中经常遇到。
def find_first_greater(arr, target):
left, right = 0, len(arr)
result = -1
while left < right:
mid = (left + right) // 2
if arr[mid] > target:
result = mid
right = mid
else:
left = mid + 1
return result
def find_last_less(arr, target):
left, right = 0, len(arr)
result = -1
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
result = mid
left = mid + 1
else:
right = mid
return result
6.3 哈希表基础
Hash Table Animation
哈希表是一种极其高效的搜索数据结构，它可以在O(1)平均时间复杂度内完成搜索、插入和删除操作。哈希表使用哈希函数将键映射到数组索引，通过索引直接访问数据。
哈希函数是哈希表的核心，它将任意大小的输入转换为固定范围的输出。好的哈希函数应该满足几个性质。确定性是指相同的输入总是产生相同的输出。均匀性是指哈希值在输出范围内均匀分布，避免集中。高效性是指计算哈希值的时间复杂度应该是O(1)。
def simple_hash(key, size):
return hash(key) % size
def string_hash(s, size):
hash_value = 0
for char in s:
hash_value = (hash_value * 31 + ord(char)) % size
return hash_value
class SimpleHashTable:
def __init__(self, size=10):
self.size = size
self.table = [None] * size
self.count = 0
def hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
if self.count >= self.size * 0.7:
self.resize()
index = self.hash(key)
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
self.table[index] = (key, value)
self.count += 1
def get(self, key):
index = self.hash(key)
start_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == start_index:
break
return None
def resize(self):
old_table = self.table
self.size *= 2
self.table = [None] * self.size
self.count = 0
for item in old_table:
if item is not None:
self.insert(item[0], item[1])
hash_table = SimpleHashTable()
hash_table.insert('apple', 10)
hash_table.insert('banana', 20)
hash_table.insert('cherry', 30)
print(f"apple的值: {hash_table.get('apple')}")
print(f"banana的值: {hash_table.get('banana')}")
哈希表的性能在很大程度上取决于哈希函数的质量。Python内置的hash函数已经经过精心设计，可以满足大多数应用场景。对于自定义哈希函数，需要特别注意均匀性和避免哈希冲突。
6.4 哈希冲突处理
哈希冲突是指不同的键被哈希函数映射到相同的索引位置。因为哈希函数的输出范围有限，而输入范围无限，哈希冲突不可避免。处理哈希冲突的方法主要有两种，链地址法和开放地址法。
链地址法将哈希表的每个位置变成一个链表，所有哈希到同一位置的键都存储在同一个链表中。这种方法简单直观，处理冲突不需要重新计算位置。但链表可能很长，导致搜索效率降低。
class ChainingHashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def get(self, key):
index = self.hash(key)
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self.hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index].pop(i)
return True
return False
开放地址法在发生冲突时，按照一定规则寻找下一个空闲位置。线性探测是最简单的开放地址法，它依次检查下一个位置，直到找到空闲位置。线性探测容易产生聚集现象，导致连续区域被占用。
class LinearProbingHashTable:
def __init__(self, size=10):
self.size = size
self.keys = [None] * size
self.values = [None] * size
self.deleted = [False] * size
def hash(self, key):
return hash(key) % self.size
def find_slot(self, key):
index = self.hash(key)
start_index = index
while self.keys[index] is not None and not self.deleted[index]:
if self.keys[index] == key:
return index, True
index = (index + 1) % self.size
if index == start_index:
return -1, False
return index, False
def insert(self, key, value):
index, found = self.find_slot(key)
if index == -1:
raise Exception("哈希表已满")
if found:
self.values[index] = value
else:
self.keys[index] = key
self.values[index] = value
self.deleted[index] = False
def get(self, key):
index, found = self.find_slot(key)
if found:
return self.values[index]
return None
def delete(self, key):
index, found = self.find_slot(key)
if found:
self.deleted[index] = True
return True
return False
二次探测和双重哈希是开放地址法的改进版本，它们可以减少聚集现象。二次探测使用二次函数计算下一个位置，双重哈希使用第二个哈希函数计算步长。这些方法可以更均匀地分布元素，减少冲突链的长度。
6.5 二叉搜索树的搜索
二叉搜索树是一种支持高效搜索的树形数据结构。在二叉搜索树中，每个节点的左子树所有节点值都小于该节点，右子树所有节点值都大于该节点。这种性质使得搜索过程可以快速缩小范围。
class BSTNode:
def __init__(self, key, value=None):
self.key = key
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None:
return None
if key == node.key:
return node.value
elif key < node.key:
return self._search(node.left, key)
else:
return self._search(node.right, key)
def insert(self, key, value=None):
self.root = self._insert(self.root, key, value)
def _insert(self, node, key, value):
if node is None:
return BSTNode(key, value)
if key < node.key:
node.left = self._insert(node.left, key, value)
elif key > node.key:
node.right = self._insert(node.right, key, value)
else:
node.value = value
return node
def find_min(self):
return self._find_min(self.root)
def _find_min(self, node):
if node is None:
return None
while node.left:
node = node.left
return node.key
def find_max(self):
return self._find_max(self.root)
def _find_max(self, node):
if node is None:
return None
while node.right:
node = node.right
return node.key
bst = BinarySearchTree()
bst.insert(50, 'A')
bst.insert(30, 'B')
bst.insert(70, 'C')
bst.insert(20, 'D')
bst.insert(40, 'E')
print(f"搜索30: {bst.search(30)}")
print(f"最小值: {bst.find_min()}")
print(f"最大值: {bst.find_max()}")
BST Search Animation
二叉搜索树的搜索时间复杂度取决于树的形状。在平衡的二叉搜索树中，搜索时间复杂度为O(log n)。在最坏情况下，树退化为链表，搜索时间复杂度为O(n)。为了保证性能，可以使用自平衡二叉搜索树如AVL树或红黑树。
二叉搜索树不仅支持搜索，还支持范围查询。可以查找所有在某个范围内的元素，通过递归遍历树的适当部分实现。这种操作在数据库索引和文件系统中经常使用。
6.6 高级搜索技术
除了基本的搜索算法，还有一些高级技术可以提高搜索效率或处理特殊场景。
跳表是一种支持快速搜索的数据结构，它通过多层索引加速搜索过程。跳表在链表基础上建立多层跳跃指针，高层指针跳过多个节点，低层指针逐步细化。跳表的搜索时间复杂度为O(log n)，比链表的O(n)快得多。
import random
class SkipListNode:
def __init__(self, key, level):
self.key = key
self.forward = [None] * level
class SkipList:
def __init__(self, max_level=4, p=0.5):
self.max_level = max_level
self.p = p
self.level = 1
self.head = SkipListNode(-1, max_level)
def random_level(self):
level = 1
while random.random() < self.p and level < self.max_level:
level += 1
return level
def insert(self, key):
update = [None] * self.max_level
current = self.head
for i in range(self.level - 1, -1, -1):
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
update[i] = current
lvl = self.random_level()
if lvl > self.level:
for i in range(self.level, lvl):
update[i] = self.head
self.level = lvl
new_node = SkipListNode(key, lvl)
for i in range(lvl):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def search(self, key):
current = self.head
for i in range(self.level - 1, -1, -1):
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
current = current.forward[0]
if current and current.key == key:
return True
return False
skip_list = SkipList()
for num in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]:
skip_list.insert(num)
print(f"搜索19: {skip_list.search(19)}")
print(f"搜索20: {skip_list.search(20)}")
Skip List Animation
布隆过滤器是一种空间效率极高的概率型数据结构，用于判断元素是否在集合中。布隆过滤器可能产生误报，但不会产生漏报。当布隆过滤器判断元素存在时，元素可能实际不存在；当判断元素不存在时，元素一定不存在。布隆过滤器适用于可以容忍误报的场景，如缓存过滤、垃圾邮件检测等。
import hashlib
class BloomFilter:
def __init__(self, size=1000, hash_count=3):
self.size = size
self.hash_count = hash_count
self.bit_array = [False] * size
def add(self, item):
for i in range(self.hash_count):
index = self._hash(item, i) % self.size
self.bit_array[index] = True
def might_contain(self, item):
for i in range(self.hash_count):
index = self._hash(item, i) % self.size
if not self.bit_array[index]:
return False
return True
def _hash(self, item, i):
return int(hashlib.md5(f'{item}{i}'.encode()).hexdigest(), 16)
bloom = BloomFilter()
bloom.add('apple')
bloom.add('banana')
print(f"'apple' 可能存在: {bloom.might_contain('apple')}")
print(f"'orange' 可能存在: {bloom.might_contain('orange')}")
Bloom Filter Animation
本章简单提了多种搜索算法。线性搜索简单但效率低，适用于小规模数据。二分搜索效率高但要求有序数据。哈希表提供接近O(1)的搜索效率，是实际应用中最重要的搜索结构。二叉搜索树结合了数组的灵活性和搜索的效率。跳表和布隆过滤器等高级技术在特定场景下有重要应用。下一章我们将学习动态规划，一种强大的算法设计技术。
预览时标签不可点