【二分查找算法】二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数组或列表。它通过将查找区间逐步缩小一半来快速定位目标值，时间复杂度为 O(log n)，远优于线性查找的 O(n)。以下是对二分查找算法的总结与对比。
一、二分查找算法简介
二分查找的基本思想是：在有序数组中，每次比较中间元素与目标值，根据比较结果决定继续在左半部分或右半部分查找，直到找到目标值或确定其不存在。
该算法要求数据必须是有序排列的，否则无法正确使用二分查找。
二、二分查找步骤说明
| 步骤 | 操作说明 |
| 1 | 确定数组的起始索引 `low` 和结束索引 `high` |
| 2 | 计算中间索引 `mid = (low + high) // 2` |
| 3 | 比较 `arr[mid]` 与目标值 `target` |
| 4 | 如果 `arr[mid] == target`，返回 `mid` |
| 5 | 如果 `arr[mid] > target`，则在左半部分查找，更新 `high = mid - 1` |
| 6 | 如果 `arr[mid] < target`，则在右半部分查找，更新 `low = mid + 1` |
| 7 | 重复步骤 2~6，直到找到目标或 `low > high` 表示未找到 |
三、二分查找优缺点对比
| 项目 | 优点 | 缺点 |
| 时间复杂度 | O(log n) 非常高效 | 要求数据必须有序 |
| 空间复杂度 | O(1)（不使用额外空间） | 不适合频繁插入/删除的动态数据结构 |
| 实现难度 | 相对简单，易于理解 | 边界条件处理容易出错 |
| 应用场景 | 适用于静态、有序数据集 | 不适用于无序或动态数据 |
四、常见实现方式
| 实现方式 | 特点 |
| 递归实现 | 代码简洁，但可能有栈溢出风险 |
| 迭代实现 | 更节省内存，性能更稳定 |
| 变体实现 | 如查找第一个/最后一个匹配项 |
五、示例代码（Python）
```python
def binary_search(arr, target):
low = 0
high = 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
```
六、总结
二分查找是一种非常实用的算法，尤其在大规模数据中具有显著的效率优势。虽然实现起来相对简单，但在实际应用中需要注意边界条件和数据是否有序的问题。对于需要频繁查询的有序数据结构，二分查找是一个理想的选择。