Python 二分查找算法详解：原理、实现与实战应用

1. 什么是二分查找二分查找Binary Search是一种在有序数组中快速查找目标元素的算法。它的核心思想是“分而治之”每次比较数组中间的元素根据比较结果将搜索范围缩小一半直到找到目标元素或搜索范围为空。二分查找的时间复杂度为O(log n)远优于线性查找的 O(n)是处理有序数据时的高效搜索算法。2. 二分查找的基本原理二分查找算法遵循以下步骤确定搜索范围的左右边界初始为数组的第一个和最后一个索引。计算中间位置mid (left right) // 2。比较中间元素与目标值如果相等返回中间索引。如果中间元素小于目标值说明目标在右半部分将左边界更新为mid 1。如果中间元素大于目标值说明目标在左半部分将右边界更新为mid - 1。重复步骤 2-3直到找到目标或左边界大于右边界未找到。3. Python 二分查找实现3.1 基础版本精确匹配def binary_search(arr, target): 在有序数组 arr 中查找 target返回其索引未找到返回 -1。 left, right 0, len(arr) - 1 while left lt; right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] lt; target: left mid 1 else: right mid - 1 return -1 示例 arr [1, 3, 5, 7, 9, 11, 13] target 7 result binary_search(arr, target) print(f元素 {target} 的索引是: {result}) # 输出: 元素 7 的索引是: 33.2 查找第一个等于目标值的位置def binary_search_first(arr, target): 在有序数组 arr 中查找第一个等于 target 的元素的索引。 如果不存在返回 -1。 left, right 0, len(arr) - 1 result -1 while left lt; right: mid (left right) // 2 if arr[mid] target: result mid right mid - 1 # 继续在左半部分查找 elif arr[mid] lt; target: left mid 1 else: right mid - 1 return result 示例 arr [1, 2, 2, 2, 3, 4, 5] target 2 result binary_search_first(arr, target) print(f第一个 {target} 的索引是: {result}) # 输出: 第一个 2 的索引是: 13.3 查找最后一个等于目标值的位置def binary_search_last(arr, target): 在有序数组 arr 中查找最后一个等于 target 的元素的索引。 如果不存在返回 -1。 left, right 0, len(arr) - 1 result -1 while left lt; right: mid (left right) // 2 if arr[mid] target: result mid left mid 1 # 继续在右半部分查找 elif arr[mid] lt; target: left mid 1 else: right mid - 1 return result 示例 arr [1, 2, 2, 2, 3, 4, 5] target 2 result binary_search_last(arr, target) print(f最后一个 {target} 的索引是: {result}) # 输出: 最后一个 2 的索引是: 34. 二分查找的变体与应用场景4.1 查找第一个大于等于目标值的位置常用于寻找插入位置或满足条件的最小值。def binary_search_first_ge(arr, target): 在有序数组 arr 中查找第一个大于等于 target 的元素的索引。 如果所有元素都小于 target返回 len(arr)。 left, right 0, len(arr) - 1 result len(arr) while left lt; right: mid (left right) // 2 if arr[mid] gt; target: result mid right mid - 1 else: left mid 1 return result 示例 arr [1, 3, 5, 7, 9] target 6 result binary_search_first_ge(arr, target) print(f第一个大于等于 {target} 的索引是: {result}) # 输出: 第一个大于等于 6 的索引是: 34.2 在旋转有序数组中查找处理部分有序数组的二分查找变体。def search_in_rotated_array(nums, target): 在旋转有序数组中查找目标值。 示例: nums [4,5,6,7,0,1,2], target 0 left, right 0, len(nums) - 1 while left lt; right: mid (left right) // 2 if nums[mid] target: return mid # 判断哪一半是有序的 if nums[left] lt; nums[mid]: # 左半部分有序 if nums[left] lt; target lt; nums[mid]: right mid - 1 else: left mid 1 else: # 右半部分有序 if nums[mid] lt; target lt; nums[right]: left mid 1 else: right mid - 1 return -1 示例 nums [4, 5, 6, 7, 0, 1, 2] target 0 result search_in_rotated_array(nums, target) print(f在旋转数组中 {target} 的索引是: {result}) # 输出: 在旋转数组中 0 的索引是: 45. 二分查找的注意事项数组必须有序二分查找的前提是数据有序否则结果不可预测。边界条件注意循环终止条件left right还是left right和边界更新mid 1或mid - 1。整数溢出在 Python 中整数不会溢出但在其他语言中计算mid (left right) // 2时left right可能溢出建议使用mid left (right - left) // 2。重复元素基础二分查找不保证返回第一个或最后一个匹配项需要根据需求选择变体。6. 实战应用6.1 在排序列表中查找元素这是二分查找最直接的应用Python 内置的bisect模块提供了高效的二分查找实现。import bisect arr [1, 3, 5, 7, 9] 查找插入位置保持有序 pos bisect.bisect_left(arr, 6) # 返回 3 print(f6 应该插入的位置: {pos}) 实际插入 bisect.insort(arr, 6) print(f插入后的数组: {arr}) # 输出: [1, 3, 5, 6, 7, 9]6.2 求解数学问题的近似解二分查找可用于求解单调函数的根或最优化问题。def sqrt_binary_search(x, epsilon1e-6): 使用二分查找计算 x 的平方根。 if x 0: raise ValueError(不能计算负数的平方根) left, right 0, max(1, x) while right - left gt; epsilon: mid (left right) / 2 if mid * mid lt; x: left mid else: right mid return (left right) / 2 示例 result sqrt_binary_search(2) print(f2 的平方根近似值: {result:.6f}) # 输出: 2 的平方根近似值: 1.4142147. 总结二分查找是计算机科学中最重要的算法之一它的高效性使其成为处理有序数据时的首选搜索算法。掌握二分查找不仅需要理解其基本原理还需要熟悉各种变体以应对不同的应用场景。在实际编程中优先考虑使用 Python 内置的bisect模块。注意边界条件和终止条件避免无限循环。根据具体需求选择合适的二分查找变体。二分查找的思想可以扩展到更多领域如数据库索引、机器学习中的超参数调优等。