实现有序数组的二分查找

题目

实现有序数组的二分查找

信息

• 类型：问答
• 难度：⭐

考点

二分查找,数组操作,边界条件处理

快速回答

二分查找是在有序数组中高效查找目标值的算法，核心步骤：

1. 确定查找范围的左右边界（初始为数组首尾索引）
2. 计算中间位置 mid = (left + right) / 2
3. 比较 mid 处的值与目标值：
   • 若相等则返回索引
   • 若目标值较小，则在左半部分继续查找（right = mid - 1）
   • 若目标值较大，则在右半部分继续查找（left = mid + 1）
4. 重复直到找到目标值或边界交叉（left > right）

时间复杂度：O(log n)，空间复杂度：O(1)

解析

原理说明

二分查找基于分治思想，通过不断将有序数组对半分割来缩小搜索范围。每次比较中间元素可将搜索空间减半，因此效率远高于顺序查找（O(n)）。

代码示例（迭代实现）

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # 避免整数溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到

最佳实践

• 循环条件：使用 left <= right 确保边界交叉时终止
• 中间值计算：mid = left + (right - left) // 2 避免整数溢出
• 边界更新：left = mid + 1 / right = mid - 1 防止死循环
• 提前终止：找到目标值立即返回

常见错误

扩展知识

• 递归实现：空间复杂度 O(log n)，适用于教学但不推荐生产环境
• 变体问题：
  • 查找第一个/最后一个等于目标值的位置
  • 查找大于等于目标值的最小元素
• 应用场景：有序集合查询（数据库索引）、数值计算（求平方根）
• 对比其他查找：
  • 顺序查找：O(n) 时间，无需有序
  • 哈希查找：O(1) 平均时间，但需要额外空间

复杂度证明

设数组长度 n，每次迭代数据量减半：n → n/2 → n/4 → ... → 1。迭代次数 k 满足 n/(2^k) = 1，解得 k = log₂n，故时间复杂度为 O(log n)。