【二分查找算法】二分查找，又称折半查找，是一种在有序数组中查找特定元素的高效算法。其核心思想是通过不断将搜索区间对半分割，逐步缩小查找范围，从而快速定位目标值。相比线性查找，二分查找的时间复杂度更低，适用于数据量较大且已排序的场景。
一、基本原理
二分查找的基本步骤如下：
1. 初始化：设定两个指针，`low` 指向数组起始位置，`high` 指向数组末尾位置。
2. 循环查找：当 `low ≤ high` 时，计算中间位置 `mid = (low + high) // 2`。
3. 比较中间值：
- 如果 `arr[mid] == target`，则返回 `mid`，表示找到目标值。
- 如果 `arr[mid] < target`，说明目标值在右半部分，更新 `low = mid + 1`。
- 如果 `arr[mid] > target`，说明目标值在左半部分，更新 `high = mid - 1`。
4. 未找到：若循环结束仍未找到目标值，则返回 `-1` 表示未找到。
二、适用条件
| 条件 | 是否满足 |
| 数据必须是有序的 | ✅ 是 |
| 数据量较大 | ✅ 是 |
| 需要频繁查找 | ✅ 是 |
| 不支持动态插入/删除 | ❌ 否 |
三、时间复杂度
| 情况 | 时间复杂度 |
| 最坏情况 | O(log n) |
| 平均情况 | 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
```
七、注意事项
- 避免整数溢出：在某些编程语言中，`(low + high)` 可能导致溢出，建议使用 `low + (high - low) // 2`。
- 边界处理：确保循环条件正确，防止死循环或越界访问。
- 数据预处理：在使用前需确认数组是否已排序，否则结果不可靠。
总结
二分查找是一种高效的查找算法，特别适合在已排序的数据集中使用。虽然它不能处理无序数据，但在实际应用中具有广泛的用途。掌握其原理与实现方式，有助于提升程序性能和解决问题的效率。