【二分法查找是什么】二分法查找，也称为二分搜索，是一种高效的查找算法，用于在有序数组中快速定位目标值。它的核心思想是通过不断将查找区间一分为二，逐步缩小范围，直到找到目标值或确认其不存在。
一、
二分法查找适用于已排序的数组或列表。它通过比较中间元素与目标值，决定继续在左半部分还是右半部分查找，从而减少不必要的比较次数。该算法的时间复杂度为 O(log n)，比线性查找（O(n)）快得多。
使用二分法时，需确保数据是有序的。如果数据未排序，需先进行排序处理，否则无法正确使用二分法。
二分法的关键步骤包括：
1. 确定查找范围的起始和结束位置；
2. 计算中间位置；
3. 比较中间元素与目标值；
4. 根据比较结果调整查找范围；
5. 重复上述步骤，直到找到目标值或查找范围为空。
二、表格展示
| 项目 | 内容 |
| 名称 | 二分法查找 / 二分搜索 |
| 类型 | 查找算法 |
| 时间复杂度 | O(log n) |
| 空间复杂度 | O(1)（非递归实现） |
| 数据要求 | 必须为有序数组 |
| 原理 | 不断将查找区间对半分割，逐步缩小范围 |
| 优点 | 查找速度快，效率高 |
| 缺点 | 需要数据预先排序，不适合动态数据 |
| 应用场景 | 在大量有序数据中快速查找目标值 |
三、适用情况与注意事项
- 适用情况：
- 数据已排序；
- 数据量较大，希望提高查找效率；
- 需要频繁查找操作。
- 注意事项：
- 若数据无序，必须先排序；
- 不能用于链表结构，因为无法快速访问中间元素；
- 对于小规模数据，线性查找可能更简单直接。
四、示例说明
假设有一个有序数组：`[1, 3, 5, 7, 9, 11, 13]`，查找目标值 `7`。
1. 初始范围：`low = 0`, `high = 6`；
2. 中间位置：`mid = (0 + 6) // 2 = 3`，对应值为 `7`；
3. 找到目标值，返回索引 `3`。
五、结语
二分法查找是一种高效、实用的算法，在计算机科学和编程中广泛应用。掌握其原理和使用条件，有助于提升程序的性能和效率。对于开发者而言，合理选择查找算法，可以显著优化程序运行时间。