二分查找 (Binary Search)

二分查找是一种在有序数组中查找特定元素的搜索算法。

其基本思想是：每次比较中间元素，将查找范围缩小一半。

算法流程

假设我们在升序数组 arr 中查找目标值 target：

1. 设置两个指针，left = 0, right = len(arr) - 1。
2. 计算中间索引 mid = (left + right) // 2。
3. 比较 arr[mid] 与 target：
   • 如果 arr[mid] == target，找到了，返回 mid。
   • 如果 arr[mid] > target，说明目标在左半边，right = mid - 1。
   • 如果 arr[mid] < target，说明目标在右半边，left = mid + 1。
4. 如果 left > right，说明找不到，返回 -1。

代码实现

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] > target:
            right = mid - 1  # 往左找
        else:
            left = mid + 1   # 往右找

    return -1  # 未找到

# 测试 (前提：数组必须有序)
nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7))  # 3
print(binary_search(nums, 4))  # -1

复杂度分析

• 时间复杂度: \(O(\log n)\)。每查找一次，范围减半。\(2^{10} \approx 1000\)，即 1000 个数只需找 10 次。
• 空间复杂度: \(O(1)\)。

常见变体

二分查找不仅仅是“找是否存在”，常见的变体还有：

1. 查找第一个出现的位置 (例如 [2, 4, 4, 4, 6], target=4, 返回 index 1)。
2. 查找最后一个出现的位置。
3. 寻找插入位置 (Python 内置 bisect 模块)。

Python 内置 bisect 库

Python 标准库提供了高效的二分查找工具：

import bisect

nums = [1, 3, 4, 4, 6]

# 寻找插入位置，保持有序
idx = bisect.bisect_left(nums, 4)
print(idx) # 2 (插在第一个 4 前面)

idx_right = bisect.bisect_right(nums, 4)
print(idx_right) # 4 (插在最后一个 4 后面)

本章小结

• 条件：数组必须是有序的。
• 边界：while left <= right 还是 left < right？right = mid 还是 mid - 1？这是二分最容易写错的地方。
  • 标准写法：right = len - 1, while left <= right, right = mid - 1。

---

下一章：动态规划