什么是二分查找

# 什么是二分查找

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

## 算法原理
1. **前提条件**  
   数组必须是有序的（升序或降序），这是二分查找能够工作的基础。

2. **操作步骤**  
   - 初始化两个指针：`low`（指向起始位置）和`high`（指向末尾位置）
   - 计算中间位置 `mid = (low + high) // 2`
   - 比较中间元素与目标值：
     - 若 `arr[mid] == target`：返回位置
     - 若 `arr[mid] < target`：在右半部分继续搜索（`low = mid + 1`）
     - 若 `arr[mid] > target`：在左半部分继续搜索（`high = mid - 1`）
   - 重复直到 `low > high`（未找到）

## 代码示例（Python）
```python
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # 未找到

时间复杂度分析

• 最优情况：O(1)（第一次就命中）
• 最坏情况：O(log n)（需要持续折半直到范围缩小为1）
• 空间复杂度：O(1)（迭代实现）

优缺点对比

实际应用场景

1. 大型数据库索引查询
2. 游戏中的分数排行榜查找
3. 系统文件按名称快速检索
4. 数值计算中的方程求根（二分法）

变体算法

• 查找第一个/最后一个等于目标值的位置
• 查找大于/小于目标值的边界
• 无限流数据中的二分查找

总结

二分查找通过”分而治之”的策略将线性时间优化为对数时间，是算法学习中必须掌握的经典范例。其高效性使其成为处理有序数据集时的首选方案。 “`