python必背源代码二分查找代码
本文提供Python必背源代码二分查找代码的标准循环模板、递归实现与处理重复元素的左右边界变体。包含完整的算法执行逻辑、推导流程图、易错边界防坑指南与内置bisect模块对比,帮助开发者快速掌握对数级高效检索。
bisect 模块的最佳实践,并梳理核心判断依据与避坑要点。
一、二分查找的前提条件与基本原理
二分查找之所以能够实现高效检索,依赖于一个严苛的前提条件:数据必须是有序的,且底层数据结构必须支持 O(1) 的随机访问(例如 Python 的列表 list)。如果要在无序序列或链表上检索,二分查找便不成立。
算法在执行时维护两个指针:left 指向当前搜索区间的起始索引,right 指向结束索引。每一次迭代计算中点索引 mid,并对比中点元素 nums[mid] 与目标值 target:
- 若 nums[mid] == target:已命中目标,直接返回当前下标
mid。 - 若 nums[mid] < target:由于数组升序排列,中点左侧所有元素都小于 target,目标只能存在于右半侧。因此更新左界
left = mid + 1。 - 若 nums[mid] > target:中点右侧所有元素都大于 target,目标只能存在于左半侧。因此更新右界
right = mid - 1。
二、最经典必背源代码:闭区间迭代实现
在实际编写和面试场景中,最不容易出错、也是各技术团队普遍认可的标准写法是闭区间迭代法(即区间定义始终为 [left, right])。以下是必须牢记的完整源代码实现:
def binary_search(nums: list[int], target: int) -> int:
"""
在升序列表 nums 中二分查找目标值 target
:param nums: 严格升序排列的整数列表
:param target: 待查找的目标数值
:return: 若找到返回对应下标,未找到返回 -1
"""
left = 0
right = len(nums) - 1 # 闭区间 [0, len(nums) - 1]
while left <= right: # 当 left == right 时,区间内还有一个元素需要检查
# 防止整型溢出的标准写法(等价于 (left + right) // 2)
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1 # 目标在右侧,排除 mid 后的新区见为 [mid + 1, right]
else:
right = mid - 1 # 目标在左侧,排除 mid 后的新区间为 [left, mid - 1]
return -1 # 循环结束未找到目标,返回 -1
完整运行示例与输出验证
可以在任意 Python 3 环境下新建脚本并执行以下测试代码:
if __name__ == "__main__":
test_cases = [
([2, 5, 8, 12, 16, 23, 38], 23), # 正常命中
([2, 5, 8, 12, 16, 23, 38], 2), # 命中首个元素
([2, 5, 8, 12, 16, 23, 38], 38), # 命中末尾元素
([2, 5, 8, 12, 16, 23, 38], 15), # 列表中不存在的目标
]
for nums, target in test_cases:
res = binary_search(nums, target)
print(f"在数组 {nums} 中查找 {target} -> 索引结果: {res}")
三个关键细节的原因解析
-
为什么循环条件是
left <= right而非left < right?
因为初始设定right = len(nums) - 1决定了搜索范围是闭区间[left, right]。当left == right时,区间如[3, 3]并非空集,依然包含下标 3 这个元素需要验证。如果漏掉等号,处于该位置的目标将被直接忽略。 -
为什么边界移动必须是
mid + 1和mid - 1?
因为在条件分支中,nums[mid] == target已经被判断并排除,当前mid绝不可能是目标。下一轮必须从排除中点后的新区间开始。如果不加减 1,当left和right相邻时会导致区间永远无法缩小,陷入死循环。 -
中点计算为什么写成
left + (right - left) // 2?
在 C/C++ 或 Java 中,直接写(left + right) // 2当两者数值很大时可能导致整型溢出。虽然 Python 具有原生任意精度大整型支持,但养成规范的算法书写习惯有助于跨语言保持一致性与严谨性。
三、必背变体一:递归实现版本
二分查找本质是分治(Divide and Conquer)思想的典型体现:把规模为 n 的问题分解为规模为 n/2 的同类子问题。在教学考核或分治题目中,面试官经常要求给出递归实现。
def binary_search_recursive(nums: list[int], target: int, left: int = 0, right: int = None) -> int:
"""
二分查找的递归实现
"""
if right is None:
right = len(nums) - 1
# 递归终止基线条件:搜索区间已失效
if left > right:
return -1
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
# 目标在右半区,递归缩小左界
return binary_search_recursive(nums, target, mid + 1, right)
else:
# 目标在左半区,递归缩小右界
return binary_search_recursive(nums, target, left, mid - 1)
两种实现的时间复杂度均为 O(log n)。但在空间复杂度上,循环迭代版仅占用 O(1) 常数辅助空间;而递归版本每一次函数调用都会压入系统调用栈,空间开销为 O(log n)。在工程中,优先推荐迭代写法以避免递归栈开销。
四、必背变体二:包含重复元素的边界查找
当有序数组中存在重复元素时(例如 nums = [1, 3, 3, 3, 5, 8],寻找 3),基础二分查找只要命中任意一个 3 就会直接返回(可能返回索引 1、2 或 3),无法确保获取首个或最后一个位置。
要解决这个问题,必须在 nums[mid] == target 时不立即返回,而是根据需求继续压迫搜索边界:
1. 寻找最左侧边界(首次出现的位置)
当命中目标时,说明左侧可能还有相同的元素,因此收缩右边界 right = mid - 1,将搜索范围锁定在当前位置的左侧。
def binary_search_left(nums: list[int], target: int) -> int:
"""
寻找目标值在有序数组中首次出现的下标,若不存在返回 -1
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
# 命中不返回,继续向左侧紧缩右边界
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# 循环退出后,检查 left 是否越界且对应的值是否确实为 target
if left < len(nums) and nums[left] == target:
return left
return -1
2. 寻找最右侧边界(最后一次出现的位置)
当命中目标时,说明右侧可能还有相同的元素,因此推进左边界 left = mid + 1,将搜索范围锁定在当前位置的右侧。
def binary_search_right(nums: list[int], target: int) -> int:
"""
寻找目标值在有序数组中最后一次出现的下标,若不存在返回 -1
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
# 命中不返回,继续向右侧推进左边界
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# 循环退出后,检查 right 是否在合法范围内且值确实为 target
if right >= 0 and nums[right] == target:
return right
return -1
五、生产环境推荐:Python 内置 bisect 模块
在实际工程开发中,除非算法面试指明需要手写,否则应当优先使用 Python 标准库中的 bisect 模块。该模块底层基于 C 语言高度优化,不仅执行性能极高,而且逻辑严谨。
| 函数名称 | 作用描述 | 与手写实现的等价关系 |
|---|---|---|
bisect.bisect_left(a, x) |
在有序列表 a 中寻找 x 的左侧插入点(即首个 >= x 的位置) | 若元素存在,返回值就是首个目标值的下标 |
bisect.bisect_right(a, x) |
在有序列表 a 中寻找 x 的右侧插入点(即首个 > x 的位置) | 若元素存在,返回值 - 1 就是最后一个目标值的下标 |
import bisect
def find_target_with_bisect(nums: list[int], target: int) -> int:
"""
利用 Python 标准库 bisect 快速定位目标元素下标
"""
idx = bisect.bisect_left(nums, target)
# bisect_left 返回的是插入位置,需要判断该位置的值是否确实等于 target
if idx < len(nums) and nums[idx] == target:
return idx
return -1
# 示例验证
arr = [1, 3, 3, 3, 5, 8]
print("查找 3 的左边界下标:", bisect.bisect_left(arr, 3)) # 输出: 1
print("查找 3 的右侧插入下标:", bisect.bisect_right(arr, 3)) # 输出: 4 (末位下标是 4 - 1 = 3)
print("查找 4 的插入点下标:", bisect.bisect_left(arr, 4)) # 输出: 4 (4 不存在)
print("工程封装函数检索 3:", find_target_with_bisect(arr, 3)) # 输出: 1
print("工程封装函数检索 7:", find_target_with_bisect(arr, 7)) # 输出: -1
六、高频陷阱与避坑全景总结
编写二分查找时,最常见的问题是出现死循环或边界越界。在编码与排查时,应严格对照以下要点:
- 序列未事先排序:二分查找对未排序数组会产生不可控的错误结果。如果数据无序且只查询一次,直接线性搜索只需 O(n),不必专门耗费 O(n log n) 进行排序。
- 死循环陷阱:更新指针时如果写成了
left = mid或right = mid,在区间长度为 2 时极易陷入循环永不退出的状态。闭区间写法下必须始终使用left = mid + 1和right = mid - 1。 - 除法符号误写:Python 中单个斜杠
/为浮点除法,得到的结果是float类型,后续作为下标访问列表会抛出TypeError: list indices must be integers or slices, not float。必须使用双斜杠整除//。 - 越界安全保护:当编写左右边界变体或使用
bisect时,返回的索引可能等于数组长度(即目标比所有元素都大),必须先判断索引合法性再索引元素。
本站声明
本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。













