【二分法查找是什么】二分法查找，又称折半查找，是一种在有序数组中查找特定元素的高效算法。它的基本思想是通过不断将搜索区间对半分割，逐步缩小目标值可能存在的范围，直到找到目标值或确认其不存在。
二分法查找适用于已排序的数据结构，例如数组或列表。由于每次操作都将搜索范围减半，因此其时间复杂度为 O(log n)，远优于线性查找的 O(n)。
二分法查找的核心步骤：
1. 初始化左右指针：左指针指向数组起始位置，右指针指向数组末尾。
2. 计算中间索引：通过 `(left + right) // 2` 计算中间位置。
3. 比较中间值与目标值：
- 如果中间值等于目标值，返回该位置。
- 如果中间值大于目标值，说明目标值在左半部分，调整右指针。
- 如果中间值小于目标值，说明目标值在右半部分，调整左指针。
4. 重复上述步骤，直到找到目标值或搜索区间为空。
二分法查找的特点总结：
| 特点 | 描述 |
| 适用条件 | 数据必须是有序的 |
| 时间复杂度 | O(log n) |
| 空间复杂度 | O(1)，无需额外空间 |
| 是否破坏原数据 | 否，仅读取不修改 |
| 是否适合大数据 | 是，效率高 |
| 是否支持重复元素 | 可以，但只能找到一个匹配项 |
二分法查找的优缺点
| 优点 | 缺点 |
| 查找速度快，尤其适合大数据量 | 必须保证数据有序 |
| 算法实现简单，逻辑清晰 | 无法直接用于无序数据 |
| 不需要额外存储空间 | 不能直接获取所有匹配项 |
示例说明（以升序数组为例）：
假设数组为 `[1, 3, 5, 7, 9, 11]`，查找目标值 `7`：
- 初始 left = 0，right = 5
- mid = (0+5)/2 = 2 → 数组值为 5，小于 7 → left = 3
- 新 mid = (3+5)/2 = 4 → 数组值为 9，大于 7 → right = 3
- 新 mid = (3+3)/2 = 3 → 数组值为 7，找到目标
总结
二分法查找是一种高效的查找方法，特别适合在已排序的数据集中使用。虽然它有严格的适用条件（数据必须有序），但在实际应用中，只要数据能够提前排序，就可以充分发挥其优势。对于大规模数据处理，二分法是不可或缺的工具之一。
