如何用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：

1. 初始范围：low = 0, high = 4。
2. 第一次计算：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 代码解释

1. 初始化范围：low 和 high 分别指向数组的首尾。
2. 循环条件：while low <= high 确保范围有效。
3. 中间索引计算：mid = (low + high) // 2（向下取整）。
4. 比较逻辑： 若 arr[mid] 等于目标，直接返回 mid。 若 arr[mid] 小于目标，目标在右半部分，因此 low = mid + 1。 反之，high = mid - 1。
5. 未找到时返回-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 -1

5.2 避免整数溢出（理论场景）

在某些语言（如 C++、Java）中，low + high 可能溢出，可用 mid = low + (high - low) // 2 替代。

六、总结步骤

1. 确保数组有序：二分搜索的前提是数组必须有序。
2. 初始化搜索范围：low 和 high 分别为数组首尾索引。
3. 循环缩小范围：通过比较中间元素调整 low 或 high。
4. 处理边界条件：确保循环终止条件正确（low <= high）。

七、练习题

1. 降序数组的二分搜索：修改代码，使算法能在降序数组中正确查找目标。
2. 查找第一个大于等于目标的元素：

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

3. 实现递归版本的边界测试：验证递归函数在空数组、单元素等场景的表现。

通过以上步骤，可以逐步掌握二分搜索的实现逻辑，并理解其高效性和适用场景。