【二分查找算法】二分查找，又称折半查找，是一种在有序数组中查找特定元素的高效算法。它通过不断将搜索区间分成两半，逐步缩小范围，最终找到目标值或确定其不存在。该算法的时间复杂度为 O(log n)，远优于线性查找的 O(n)。
一、二分查找的基本原理
1. 前提条件：数组必须是有序的（升序或降序）。
2. 步骤：
- 确定数组的左右边界（left 和 right）。
- 计算中间位置 mid = (left + right) // 2。
- 比较中间元素与目标值：
- 如果相等，返回 mid；
- 如果中间元素大于目标值，则在左半部分继续查找；
- 如果中间元素小于目标值，则在右半部分继续查找。
3. 终止条件：当 left > right 时，说明未找到目标值。
二、二分查找的实现方式
| 方法 | 描述 | 特点 |
| 递归实现 | 使用递归函数调用自身进行查找 | 代码简洁，但可能有栈溢出风险 |
| 迭代实现 | 使用循环结构进行查找 | 效率更高，更常用 |
| 变体实现 | 如查找第一个/最后一个匹配项、处理重复元素 | 更加灵活，适用于不同场景 |
三、二分查找的应用场景
| 场景 | 说明 |
| 数据库查询 | 快速定位记录 |
| 数组查找 | 在已排序数组中快速查找元素 |
| 搜索算法优化 | 提高搜索效率，减少比较次数 |
| 面试题 | 常见于算法类面试题中 |
四、二分查找的优缺点
| 优点 | 缺点 |
| 时间复杂度低，效率高 | 要求数据必须有序 |
| 实现简单，逻辑清晰 | 无法直接用于无序数据 |
| 适用于大规模数据集 | 不适合频繁插入/删除操作 |
五、二分查找的注意事项
- 数组是否有序：若未排序，需先排序后再使用。
- 边界条件处理：注意 left 和 right 的更新逻辑，避免死循环。
- 重复元素处理：若存在多个相同元素，需根据需求调整查找策略（如找第一个或最后一个）。
- 索引计算：mid = left + (right - left) // 2，可避免整数溢出问题。
六、示例代码（Python）
```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
```
七、总结
二分查找是一种非常实用且高效的算法，尤其在处理大量有序数据时表现出色。掌握其基本原理和实现方式，有助于提升编程能力和算法思维。同时，了解其适用范围和限制条件，可以避免在不合适的场景下误用该算法。