二分搜索

二分搜索（Binary Search）是一种在有序数组中高效查找特定元素的算法，其时间复杂度为$O(\log n)$，远优于线性搜索的$O(n)$。它是计算机科学中最基础且广泛应用的算法之一，适用于排序后的数据集合。

算法原理

二分搜索通过反复将搜索区间减半来定位目标值。具体步骤如下： 1. 初始化两个指针：left（指向数组起始）和right（指向数组末尾）。 2. 计算中间索引mid = left + (right - left) // 2（避免整数溢出）。 3. 比较中间元素与目标值：

  * 若相等，返回索引。
  * 若中间元素小于目标值，调整left = mid + 1。
  * 若中间元素大于目标值，调整right = mid - 1。

4. 重复步骤2-3，直到left > right（未找到目标）。

可视化流程

graph TD A[数组: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91] --> B[目标: 23] B --> C{比较中间元素} C -->|mid=16 < 23| D[搜索右半部分: 23, 38, 56, 72, 91] D --> E{新的中间元素} E -->|mid=56 > 23| F[搜索左半部分: 23, 38] F --> G{找到23, 返回索引5}

代码实现

以下是Python实现示例：

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  # 未找到

# 示例
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
print(f"索引位置: {binary_search(arr, target)}")  # 输出: 索引位置: 5

复杂度分析

• 时间复杂度: $O(\log n)$ —— 每次迭代将搜索范围减半。
• 空间复杂度: $O(1)$ —— 仅需常数空间存储指针。

变体与应用

变体示例

1. 查找第一个/最后一个匹配项: 修改相等时的处理逻辑。 2. 旋转有序数组搜索: 处理部分有序数据（如[4,5,6,1,2,3]）。

实际应用

• 数据库索引: B树/B+树中的二分查找加速查询。
• 游戏开发: 在排序的分数表中快速定位玩家排名。
• 数值计算: 求解方程的近似解（如二分法求根）。

常见错误与注意事项

1. 边界条件: 确保循环终止条件为left <= right而非left < right。 2. 整数溢出: 使用mid = left + (right - left) // 2而非(left + right) // 2。 3. 未排序输入: 必须预先排序数组，否则结果无效。

练习建议

1. 实现递归版本的二分搜索。 2. 解决LeetCode问题「34. 在排序数组中查找元素的第一个和最后一个位置」。 3. 尝试在非数值数据（如字符串）上应用二分搜索。