【二分查找算法】二分查找，又称折半查找，是一种在有序数组中查找特定元素的高效算法。其核心思想是通过不断将搜索区间对半分割，逐步缩小目标值的可能范围，从而快速定位目标。
一、算法原理总结
二分查找适用于已排序的数组，且要求数组中的元素按升序或降序排列。算法的基本步骤如下：
1. 初始化左右边界：设定左指针 `left` 和右指针 `right`，分别指向数组的起始和末尾位置。
2. 计算中间位置：通过 `(left + right) // 2` 计算中间索引 `mid`。
3. 比较中间值与目标值：
- 如果 `array[mid] == target`，说明找到目标值，返回 `mid`。
- 如果 `array[mid] < target`，说明目标值在右半部分，调整左边界为 `mid + 1`。
- 如果 `array[mid] > target`，说明目标值在左半部分，调整右边界为 `mid - 1`。
4. 重复上述过程，直到找到目标值或搜索区间为空。
二、算法特点总结
| 特点 | 描述 |
| 时间复杂度 | O(log n) |
| 空间复杂度 | O(1)（非递归实现） |
| 是否需要排序 | 需要数组已排序 |
| 是否稳定 | 是（不改变原数组顺序） |
| 是否支持重复元素 | 可以，但返回的是任意一个匹配项 |
三、适用场景
- 数据量较大时，优于线性查找。
- 数据已经排序的情况下使用效果最佳。
- 用于查找有序数组中的特定元素。
四、常见错误与注意事项
| 错误类型 | 说明 |
| 数组未排序 | 二分查找仅适用于有序数组，否则结果不可靠。 |
| 边界条件处理不当 | 如 `left <= right` 或 `left < right` 的判断容易出错。 |
| 中间值计算方式不当 | 使用 `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
```
六、总结
二分查找是一种高效的查找算法，特别适合在大规模数据集中进行快速定位。虽然实现简单，但在实际应用中仍需注意边界条件和数组排序的问题。掌握好这一算法，可以显著提升程序运行效率，尤其在处理大数据时表现优异。