预计阅读 23 分钟
大海捞针的艺术 —— 查找算法
在100万条数据中找到目标，最笨的方法需要100万次比较，最聪明的方法只需要20次。查找算法教你如何聪明地”缩小范围”。
📋 开篇自测：你已经知道多少？
- 为什么二分查找要求数据必须是有序的？如果数据无序，有没有办法加速查找？
- 二分查找看似简单，但”在一个有序数组中查找第一个等于目标值的元素”你能bug-free地写出来吗？
- 搜索引擎在几十亿网页中找到你要的内容，用的是什么查找技术？
一、线性查找——最朴素的起点
最简单的查找方法：从头到尾逐个检查，直到找到目标或遍历完毕。
def linear_search(arr, target):
"""线性查找：逐个比较"""
for i, val in enumerate(arr):
if val == target:
return i
return -1
data = [4, 2, 7, 1, 9, 3, 5]
print(linear_search(data, 9)) # 4
print(linear_search(data, 6)) # -1时间复杂度： O(n)
线性查找不要求数据有序，实现简单，在小数据量时完全够用。但当数据量达到百万甚至上亿时，O(n)就不够看了。
这就像你在一个没有任何标记的图书馆里找一本书——只能从第一个书架开始，一本一本地翻过去看书名。
二、二分查找——每次排除一半
核心思想
如果数据是有序的，我们可以每次用中间元素和目标值比较，从而排除一半的数据。
这就像猜数字游戏：“我心里想了一个1到100的数，你来猜，每次我告诉你猜大了还是猜小了。“最优策略是什么？先猜50。如果被告知”大了”，就在1-49里猜；如果”小了”，就在51-100里猜。每次范围缩小一半，最多7次就能猜中。
def binary_search(arr, target):
"""二分查找：在有序数组中查找目标值"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # Python中整数无溢出问题，但在Java/C++中这样写可防止溢出，是跨语言的好习惯
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(data, 7)) # 3
print(binary_search(data, 8)) # -1时间复杂度： O(log n) 空间复杂度： O(1)
来感受一下O(log n)的威力：
| 数据量 | 线性查找最大次数 | 二分查找最大次数 |
|---|---|---|
| 100 | 100 | 7 |
| 10,000 | 10,000 | 14 |
| 1,000,000 | 1,000,000 | 20 |
| 10亿 | 10亿 | 30 |
10亿条数据，只需要30次比较！这就是对数增长的魅力。
二分查找的前提条件
- 数据必须有序 —— 这是二分查找的前提。如果数据无序，要么先排序（O(n log n)），要么用哈希表。
- 数据必须支持随机访问 —— 数组可以，链表不行（链表无法O(1)访问中间元素）。
🤔 想一想 二分查找的时间复杂度是O(log n)，排序的时间复杂度是O(n log n)。如果一个无序数组只需要查找一次，先排序再二分查找值得吗？如果需要查找很多次呢？
三、二分查找的四种变体——面试官最爱考的
基本的二分查找容易理解，但面试中经常考的是它的变体。这些变体处理的是”有重复元素的有序数组”中的精准定位问题。
变体1：查找第一个等于目标值的元素
def find_first(arr, target):
"""找到第一个等于target的元素的索引"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # 关键：找到了不停下，继续往左找
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
data = [1, 3, 5, 5, 5, 7, 9]
print(find_first(data, 5)) # 2（第一个5的位置）变体2：查找最后一个等于目标值的元素
def find_last(arr, target):
"""找到最后一个等于target的元素的索引"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # 关键：找到了不停下，继续往右找
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
data = [1, 3, 5, 5, 5, 7, 9]
print(find_last(data, 5)) # 4（最后一个5的位置）变体3：查找第一个大于等于目标值的元素
def find_first_ge(arr, target):
"""找到第一个大于等于target的元素的索引（下界）"""
left, right = 0, len(arr) - 1
result = len(arr) # 如果所有元素都小于target
while left <= right:
mid = left + (right - left) // 2
if arr[mid] >= target:
result = mid
right = mid - 1
else:
left = mid + 1
return result
data = [1, 3, 5, 7, 9, 11]
print(find_first_ge(data, 6)) # 3（第一个>=6的是7，索引3）
print(find_first_ge(data, 5)) # 2（第一个>=5的是5，索引2）变体4：查找最后一个小于等于目标值的元素
def find_last_le(arr, target):
"""找到最后一个小于等于target的元素的索引（上界）"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] <= target:
result = mid
left = mid + 1
else:
right = mid - 1
return result
data = [1, 3, 5, 7, 9, 11]
print(find_last_le(data, 6)) # 2（最后一个<=6的是5，索引2）
print(find_last_le(data, 7)) # 3（最后一个<=7的是7，索引3）这四种变体的关键区别在于：找到目标后是继续往左找还是往右找。 掌握了这个核心差异，就能应对各种二分变体题。
四、二分查找的扩展应用
应用1：求平方根
求一个数的平方根（精确到小数点后6位），这其实也是一个二分查找问题。
def sqrt_binary(n, precision=1e-6):
"""用二分法求平方根"""
if n < 0:
raise ValueError("负数没有实数平方根")
if n < 1:
left, right = 0, 1
else:
left, right = 0, n
while right - left > precision:
mid = (left + right) / 2
if mid * mid < n:
left = mid
else:
right = mid
return round((left + right) / 2, 6)
print(sqrt_binary(2)) # 1.414214
print(sqrt_binary(9)) # 3.0
print(sqrt_binary(0.25)) # 0.5应用2：查找旋转排序数组
一个有序数组在某个位置被”旋转”了，比如 [4,5,6,7,0,1,2]（原来是 [0,1,2,4,5,6,7]）。如何在这样的数组中查找目标值？
def search_rotated(arr, target):
"""在旋转排序数组中查找"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# 判断哪半边是有序的
if arr[left] <= arr[mid]: # 左半边有序
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半边有序
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
data = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(data, 0)) # 4
print(search_rotated(data, 3)) # -1应用3：查找峰值元素
在一个数组中，找到任意一个比左右邻居都大的”峰值”元素。
def find_peak(arr):
"""二分查找峰值元素"""
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1 # 峰值在右边
else:
right = mid # 峰值在左边（包括mid）
return left
data = [1, 3, 5, 4, 2]
print(find_peak(data)) # 2（arr[2]=5是峰值）🤔 想一想 上面的峰值查找算法为什么能用二分？因为如果mid位置的值比右边小，说明从mid到右边一定存在一个”先升后降”的趋势，峰值必然在右半边。这和有序数组不同，但二分的本质——每次能排除一半——仍然成立。
五、插值查找与指数查找
插值查找——更聪明的猜测
二分查找每次都猜中间位置。但如果数据分布均匀，我们可以根据目标值在范围中的相对位置来猜一个更可能的位置。
这就像你查字典找”python”——你不会翻到正中间，而是会翻到大约3/4的位置，因为p在字母表的后半段。
def interpolation_search(arr, target):
"""插值查找：根据值的分布来估计位置"""
left, right = 0, len(arr) - 1
while left <= right and arr[left] <= target <= arr[right]:
if arr[left] == arr[right]:
if arr[left] == target:
return left
break
# 关键公式：按比例估算目标位置
pos = left + int((target - arr[left]) * (right - left)
/ (arr[right] - arr[left]))
if arr[pos] == target:
return pos
elif arr[pos] < target:
left = pos + 1
else:
right = pos - 1
return -1
# 对均匀分布的数据效果最好
data = list(range(0, 1000, 2)) # [0, 2, 4, 6, ..., 998]
print(interpolation_search(data, 678)) # 339时间复杂度： 数据均匀分布时O(log log n)，最坏O(n)
指数查找——先确定范围再二分
当你面对的数据量未知或者非常大时，指数查找先以指数级增长步长确定一个范围，然后在该范围内做二分查找。
def exponential_search(arr, target):
"""指数查找"""
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 - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
data = list(range(100))
print(exponential_search(data, 67)) # 67六、实际工程中的查找
在真实项目中，查找往往不是简单地在一个内存数组里找数据。
数据库查询： 数据库使用B+树索引。B+树是一种多路搜索树，每个节点可以有几百个子节点，树的高度通常只有3-4层。这意味着在几十亿条数据中，只需要3-4次磁盘读取就能定位到目标数据。
搜索引擎： 使用倒排索引。为每个关键词建立一个列表，记录包含这个词的所有网页。搜索时，先查索引找到候选网页，再排序返回结果。
Python中的查找：
# 使用bisect模块进行二分查找
import bisect
sorted_data = [1, 3, 5, 7, 9, 11, 13, 15]
# 查找插入位置
pos = bisect.bisect_left(sorted_data, 7)
print(pos) # 3
# 等价于"查找第一个>=target的位置"
pos = bisect.bisect_left(sorted_data, 6)
print(pos) # 3（6应该插在7前面）
# bisect_right返回的是最后一个<=target的后一个位置
pos = bisect.bisect_right(sorted_data, 7)
print(pos) # 4⚠️ 常见误区
- 误区1：“二分查找很简单” —— 基本版确实简单，但变体版（查找第一个/最后一个/边界值）很容易写出死循环或返回错误结果。Knuth曾说过：虽然二分查找的思路在1946年就被提出了，但第一个没有bug的实现要到1962年才出现。
- 误区2：“查找之前一定要先排序” —— 如果只查找一次，排序（O(n log n)）再二分（O(log n)）不如直接线性查找（O(n)）。只有需要多次查找时，先排序才划算。
- 误区3：“二分查找只能用在有序数组上” —— 二分查找的本质是每次能排除一半的搜索空间。只要满足这个条件，就能用二分。旋转数组、峰值查找、数学函数求零点都是例子。
📝 掌握度自测
- 概念题： 为什么说
mid = left + (right - left) // 2比mid = (left + right) // 2更好？ - 编码题： 在有序数组
[1,2,2,2,3,4,5]中，使用二分查找统计数字2出现了多少次。 - 分析题： 如果一个有序数组有10亿个元素，每个元素4字节，总共约4GB。二分查找时，每次访问中间元素可能导致缓存未命中。和线性查找（顺序访问，对缓存友好）相比，二分查找一定更快吗？
- 编码题： 实现一个函数，在旋转排序数组中找到最小值。比如
[4,5,6,7,0,1,2]的最小值是0。 - 思考题： 假设你需要在一个极大的有序文件（无法完全加载到内存）中查找一个值，你会怎么做？
💡 自我评估
- 全部答对：二分查找已经是你的拿手好戏了。
- 答对3-4题：理解到位，把变体版多练几遍就完美了。
- 答对1-2题：建议在纸上模拟二分查找的每一步，特别注意left和right的更新逻辑。
- 全部答错：不用担心，二分查找是公认的”看着简单写起来难”。建议从最基本的版本开始，逐步过渡到变体。
前面学的数据结构——数组、链表、栈、队列、哈希表、树——每个元素之间的关系都有某种限制。接下来要登场的”图”则是最自由的数据结构：任何节点之间都可以有连接，没有任何限制。社交网络、地铁线路、互联网的拓扑——都是图。下一章，我们进入图的世界。
购买课程解锁全部内容
刷题到通关：数据结构与算法面试实战
¥29.90