【二分查找算法】二分查找，又称折半查找，是一种在有序数组中查找特定元素的高效算法。它通过不断将搜索区间分成两半，逐步缩小目标值可能存在的范围，从而实现快速定位。相比于线性查找，二分查找的时间复杂度更低，适用于大规模数据的查找操作。
一、基本原理
二分查找的核心思想是：在已排序的数组中，每次将中间元素与目标值比较，根据比较结果决定继续在左半部分或右半部分查找。这一过程重复进行，直到找到目标值或确认其不存在。
二、适用条件
- 数组必须是有序排列的（升序或降序）。
- 数据量较大时效率较高，但不适用于频繁插入或删除操作的数据结构。
三、算法步骤
1. 初始化两个指针，`low` 和 `high`，分别指向数组的起始和末尾位置。
2. 循环执行以下操作，直到 `low > high`：
- 计算中间索引 `mid = (low + high) // 2`。
- 比较 `arr[mid]` 与目标值 `target`：
- 如果相等，返回 `mid`。
- 如果 `arr[mid] < target`，说明目标在右半部分，设置 `low = mid + 1`。
- 如果 `arr[mid] > target`，说明目标在左半部分，设置 `high = mid - 1`。
3. 若循环结束仍未找到目标值，返回 `-1` 表示未找到。
四、时间复杂度分析
| 情况 | 时间复杂度 |
| 最坏情况 | O(log n) |
| 平均情况 | O(log n) |
| 最好情况 | O(1) |
其中，n 为数组长度。
五、优缺点对比
| 优点 | 缺点 |
| 查找效率高，适合大数据量 | 必须保证数组有序，否则无法使用 |
| 算法逻辑清晰，易于实现 | 不适用于动态数据结构（如链表） |
| 可用于查找最小/最大满足条件的值 | 中间值计算可能导致整数溢出（需注意处理） |
六、应用场景
- 在数据库中查找记录（尤其是索引字段）。
- 在编程竞赛中处理有序数组问题。
- 需要快速查找的系统中，如搜索引擎、字典等。
七、常见错误与注意事项
- 数组未排序：导致查找结果错误。
- 边界条件处理不当：如 `low` 和 `high` 的初始值设置错误。
- 整数溢出：当 `low + high` 超过整数范围时，应使用 `mid = low + (high - low) // 2` 来避免溢出。
八、总结
二分查找是一种基础但非常实用的算法，尤其在处理有序数据时表现出色。虽然它的应用有一定的前提条件，但在实际开发中，掌握其原理和正确使用方法是非常重要的。合理运用二分查找，可以显著提升程序的运行效率。
表格总结
| 项目 | 内容 |
| 算法名称 | 二分查找算法 |
| 核心思想 | 通过不断缩小搜索区间，提高查找效率 |
| 适用条件 | 数组必须有序 |
| 时间复杂度 | O(log n) |
| 优点 | 高效、逻辑清晰、可扩展性强 |
| 缺点 | 必须有序、不适用于动态数据结构 |
| 应用场景 | 数据库查询、编程竞赛、快速查找需求等 |
| 常见错误 | 数组未排序、边界处理不当、整数溢出 |
