如何用Python实现二分搜索算法
二分搜索（Binary Search）是一种高效的查找算法，适用于在有序数组中快速定位目标值。其核心思想是通过不断缩小搜索范围，每次将问题规模减半，时间复杂度为 (O(log n))。以下是逐步讲解实现过程：
一、二分搜索的原理
1. 核心思想
- 前提条件：数组必须是有序的（升序或降序，通常默认升序）。
- 步骤：
（1）确定搜索范围：初始范围为整个数组的起始索引 low 和结束索引 high。
（2）计算中间索引：mid = (low + high) // 2。
（3）比较中间元素： 如果 arr[mid] == target，返回 mid。 如果 arr[mid] < target low='mid' 1 arrmid> target，目标在左半部分，调整 high = mid - 1。
（4）重复步骤，直到找到目标或搜索范围无效（low > high）。
2. 示例演示
以数组 [1, 3, 5, 7, 9] 为例，查找目标 5：
- 初始范围：low = 0, high = 4。
- 第一次计算：mid = (0+4)//2 = 2，arr[2]=5，直接返回 2。
二、实现步骤
1. 确定搜索范围
- 初始 low = 0，high = len(arr)-1。
2. 循环条件
- 当 low <= high 时继续循环，否则说明未找到目标。
3. 计算中间索引
- mid = (low + high) // 2（注意：避免整数溢出，但 Python 中无需担心）。
4. 调整搜索范围
- 根据 arr[mid] 与目标值的比较结果，更新 low 或 high。
三、Python代码实现
3.1 迭代版本（推荐）
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
mid_val = arr[mid]
if mid_val == target:
return mid # 找到目标，返回索引
elif mid_val < target:
low = mid + 1 # 目标在右半部分
else:
high = mid - 1 # 目标在左半部分
return -1 # 未找到，返回-1
# 测试
test_list = [1, 3, 5, 7, 9]
print(binary_search(test_list, 5)) # 输出：2
print(binary_search(test_list, 2)) # 输出：-1
3.2 代码解释
- 初始化范围：low 和 high 分别指向数组的首尾。
- 循环条件：while low <= high 确保范围有效。
- 中间索引计算：mid = (low + high) // 2（向下取整）。
- 比较逻辑： 若 arr[mid] 等于目标，直接返回 mid。 若 arr[mid] 小于目标，目标在右半部分，因此 low = mid + 1。 反之，high = mid - 1。
- 未找到时返回-1：循环结束仍未找到，说明数组中无该元素。
3.3 递归版本（可选）
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid+1, high)
else:
return binary_search_recursive(arr, target, low, mid-1)
# 调用示例
test_list = [1, 3, 5, 7, 9]
print(binary_search_recursive(test_list, 5, 0, len(test_list)-1)) # 输出：2
四、测试与验证
4.1 正常测试
test_list = [2, 4, 6, 8, 10]
print(binary_search(test_list, 6)) # 输出：2
print(binary_search(test_list, 5)) # 输出：-1
4.2 边界测试
- 空数组：binary_search([], 5) → 返回 -1。
- 单元素数组：binary_search([5], 5) → 返回 0。
- 目标在首/尾元素：
（1）binary_search([1,2,3], 1) → 0
（2）binary_search([1,2,3], 3) → 2
五、优化与注意事项
5.1 处理重复元素
若数组中有重复值，二分搜索可能返回任意一个匹配的索引。若需找到第一个出现的位置或最后一个位置，需调整条件：
- 第一个出现的位置：
while low <= high:
mid = (low + high) // 2
if arr[mid] < target:
low = mid + 1
else:
high = mid - 1
if low < len(arr) and arr[low] == target:
return low
else:
return -15.2 避免整数溢出（理论场景）
在某些语言（如 C++、Java）中，low + high 可能溢出，可用 mid = low + (high - low) // 2 替代。
六、总结步骤
- 确保数组有序：二分搜索的前提是数组必须有序。
- 初始化搜索范围：low 和 high 分别为数组首尾索引。
- 循环缩小范围：通过比较中间元素调整 low 或 high。
- 处理边界条件：确保循环终止条件正确（low <= high）。
七、练习题
- 降序数组的二分搜索：修改代码，使算法能在降序数组中正确查找目标。
- 查找第一个大于等于目标的元素：
def find_first_ge(arr, target):
low, high = 0, len(arr)-1
res = -1
while low <= high: mid='(low' high 2 if arrmid>= target:
res = mid
high = mid - 1
else:
low = mid + 1
return res- 实现递归版本的边界测试：验证递归函数在空数组、单元素等场景的表现。
通过以上步骤，可以逐步掌握二分搜索的实现逻辑，并理解其高效性和适用场景。