实现二分查找算法 -

题目

实现二分查找算法

信息

类型：问答
难度：⭐

考点

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

快速回答

二分查找是一种在有序数组中快速定位目标值的算法：

时间复杂度：O(log n)
核心步骤：
1. 定义左右指针（初始为数组首尾）
2. 计算中间索引 mid = (left + right) / 2
3. 比较 mid 处的值与目标值
4. 根据比较结果调整左右边界
终止条件：left > right 或找到目标值

## 解析

原理说明

二分查找基于分治思想，通过不断将搜索范围减半来定位目标值。要求输入数组必须有序（升序或降序）。算法通过比较中间元素与目标值：

若相等 → 返回索引
若目标值较大 → 在右半部分继续搜索
若目标值较小 → 在左半部分继续搜索

代码示例（Python）

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:
            left = mid + 1  # 目标在右侧
        else:
            right = mid - 1  # 目标在左侧
    return -1  # 未找到

# 示例用法
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5))  # 输出: 2
print(binary_search(arr, 10)) # 输出: -1

最佳实践

边界处理：使用 left <= right 而非 left < right 确保最后一个元素被检查
防溢出：大数组计算 mid 时用 left + (right - left) // 2 避免整数溢出
循环条件：终止条件是 left > right（搜索空间为空）

常见错误

死循环：忘记更新 left/right 或错误更新（如 right = mid 而非 mid-1）
边界遗漏：使用 left < right 导致漏查单个元素的情况
无序输入：未验证数组有序性导致结果错误

时间复杂度分析

每次迭代将搜索范围减半：
n → n/2 → n/4 → ... → 1
迭代次数 = log₂n → O(log n)

扩展知识

变体问题：查找第一个/最后一个匹配项（需要调整相等时的逻辑）

递归实现：

def binary_search_rec(arr, left, right, target):
    if left > right: return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, mid+1, right, target)
    else:
        return binary_search_rec(arr, left, mid-1, target)