什么是二分查找？

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效搜索算法。其核心思想是通过不断缩小搜索范围来快速定位目标元素，时间复杂度为O(log n)，远优于线性查找的O(n)。

算法工作原理

1. 确定数组的初始边界：left = 0, right = len(arr)-1
2. 当left ≤ right时：
   • 计算中间索引：mid = (left + right) // 2
   • 比较arr[mid]与目标值target：
     • arr[mid] == target → 找到目标，返回mid
     • arr[mid] < target → 目标在右侧，调整左边界：left = mid + 1
     • arr[mid] > target → 目标在左侧，调整右边界：right = mid - 1
3. 若循环结束未找到，返回-1

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

# 测试示例
if __name__ == "__main__":
    data = [2, 4, 6, 8, 10, 12, 14]
    print(binary_search(data, 8))  # 输出: 3
    print(binary_search(data, 9))  # 输出: -1

关键注意事项

• 有序数组：输入数组必须预先排序
• 边界条件：
  • 循环条件使用left <= right而非<
  • 更新边界时需±1避免死循环
• 整数溢出问题：mid = left + (right - left) // 2
• 重复元素：返回的索引不保证是第一个/最后一个匹配项

时间复杂度分析

实际应用场景

• 大型有序数据集查询（数据库索引）
• 数值计算（求平方根）
• 游戏开发（伤害值范围匹配）
• 版本控制系统（查找引入bug的提交）
• 机器学习（超参数调优）

常见变体

• 查找第一个匹配项：处理重复元素
• 旋转数组查找：处理部分有序数组
• 无限流查找：未知长度的数据流
• 二维矩阵查找：行列有序的矩阵