【什么是二分法】二分法是一种在计算机科学和数学中广泛应用的算法，主要用于在有序数组中查找特定元素。它的核心思想是通过不断将搜索区间对半分割，逐步缩小目标值的可能范围，从而高效地找到目标元素或确定其不存在。
二分法的关键在于数据必须是有序的，这样才能保证每次分割后能够准确判断目标值所在的区间。相比线性查找，二分法在大规模数据中效率更高，时间复杂度为 O(log n)。
二分法的核心步骤：
1. 初始化左右指针：左指针 `left` 指向数组起始位置，右指针 `right` 指向数组末尾。
2. 循环条件：当 `left <= right` 时继续循环。
3. 计算中间索引：`mid = (left + right) // 2`。
4. 比较中间值与目标值：
- 如果 `arr[mid] == target`，则返回 `mid`。
- 如果 `arr[mid] < target`，说明目标在右侧，更新 `left = mid + 1`。
- 如果 `arr[mid] > target`，说明目标在左侧，更新 `right = mid - 1`。
5. 未找到目标：循环结束仍没找到，则返回 `-1` 或提示不存在。
二分法的特点总结：
| 特点 | 描述 |
| 时间复杂度 | O(log n) |
| 空间复杂度 | O(1)（原地操作） |
| 数据要求 | 必须是有序数组 |
| 适用场景 | 查找、搜索、排序等 |
| 优点 | 高效，适用于大数据集 |
| 缺点 | 不适合无序数据 |
二分法的应用场景：
- 在数据库中进行快速查询
- 在编程语言的标准库中实现查找功能（如 Java 的 `Arrays.binarySearch()`）
- 在算法题中解决“寻找目标值”类问题
- 在排序后的数组中查找最小值、最大值或特定条件的值
总结：
二分法是一种基于分治策略的高效查找算法，适用于有序数据集。它通过不断缩小搜索范围，快速定位目标元素，是算法学习中的基础且重要内容。掌握二分法不仅能提升编程能力，还能在实际开发中提高程序性能。