搜索算法对比：O(n) 与 O(log n) 的实战选择指南
面对百万级元素的数组，线性搜索最坏需执行 1000 万次操作；而二分搜索仅需 24 次比较即可完成。本文深入剖析 Python 中四大搜索算法——涵盖时间复杂度、实际权衡取舍及真实业务场景下的选型策略。包含防整数溢出实现、lower_bound/upper_bound 边界查找，以及可直接用于 LeetCode 的高质量示例。
搜索问题定义：给定集合 arr，查找目标值 target 的索引；若不存在则返回 -1。该集合可能是已排序或未排序的，也可能是静态数据或动态更新的。典型应用场景包括电商 SKU 查询（SKU 数量达百万级）和金融科技中的交易 ID 校验。
未排序数据的线性搜索
适用于任意类型集合，按顺序逐个比对元素。
实现代码：
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1复杂度分析：
- 时间：最坏/平均 O(n)，最优 O(1)。
- 空间：O(1)。
二分搜索及其变体
要求输入数组已排序。通过反复将搜索区间减半来定位目标。
迭代式实现： 使用 mid = left + (right - left) // 2 避免整数溢出（C++/Java 中至关重要；Python 中虽安全，但属行业最佳实践）。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
def upper_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
# 示例
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5)) # 3
print(lower_bound(sorted_arr, 3)) # 1
print(upper_bound(sorted_arr, 3)) # 3复杂度： 时间 O(log n)，空间 O(1)。
lower_bound 返回 target 最左侧可插入位置（即首个 ≥ target 的索引）；upper_bound 返回最右侧可插入位置（即首个 > target 的索引）。二者是处理重复元素、解决「在排序数组中查找元素第一次和最后一次出现位置」等 LeetCode 经典题型的核心工具。
指数搜索：应对流式数据或未知长度场景
适用于长度未知的已排序数组，或当目标值大概率靠近数组起始位置时。先以指数方式快速定位上界范围，再在该范围内执行二分搜索。
def exponential_search(arr, target):
if not arr:
return -1
if arr[0] == target:
return 0
bound = 1
while bound < len(arr) and arr[bound] < target:
bound *= 2
left = bound // 2
right = min(bound, len(arr) - 1)
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 示例
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456)) # 123456复杂度： 平均 O(log i)（i 为目标索引），最坏 O(log n)，空间 O(1)。
基于哈希的搜索：动态集合的首选方案
借助哈希表（Python 中的 set/dict）实现平均 O(1) 查找速度。
def hash_search_set(arr, target):
s = set(arr)
return target in s
def hash_search_dict(pairs, key):
d = dict(pairs)
return d.get(key)
# 示例
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30)) # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b")) # 2复杂度： 平均 O(1)，最坏 O(n)（哈希冲突严重时），空间 O(n)。
算法选型决策指南
- 未排序数组： 元素数量 N < 100 或查询频次极低时，选用线性搜索。
- 已排序且静态数据： 首选二分搜索。
- 需频繁插入的动态数据： 若无需维持顺序，哈希表是更优解。
- 流式数据或长度未知： 指数搜索更高效。
| 算法 | 平均时间 | 最坏时间 | 空间 | 前置条件 |
|------|----------|----------|------|----------|
| 线性搜索 | O(n) | O(n) | O(1) | 无限制 |
| 二分搜索 | O(log n) | O(log n) | O(1) | 已排序 |
| 指数搜索 | O(log i) | O(log n) | O(1) | 已排序 |
| 哈希搜索 | O(1) | O(n) | O(n) | 键可哈希 |
核心结论
- 对于 1000 万个元素：二分搜索约需 24 次比较，线性搜索最坏需 1000 万次。
- 二分搜索中务必采用防溢出的
mid计算方式——即使在 Python 中，这也是提升代码健壮性的关键习惯。 - 哈希表以 O(n) 内存为代价，换取平均 O(1) 的极致查询性能。
lower_bound与upper_bound是处理重复值、实现精准插入逻辑的必备工具。- 当海量已排序数组中目标值高度集中在开头时，指数搜索优势显著。
— Editorial Team
暂无评论。