【数据结构折半查找】在数据结构中，折半查找（也称为二分查找）是一种高效的查找算法，适用于已排序的线性表。其基本思想是通过不断将查找区间对半分割，逐步缩小目标值可能存在的范围，从而快速定位目标元素的位置。
折半查找的时间复杂度为 O(log n)，相较于顺序查找的 O(n)，在大规模数据中具有显著优势。但需要注意的是，该算法要求数据必须是有序排列的，否则无法正确执行。
折半查找的基本步骤如下：
1. 确定查找区间的起始位置 `low` 和结束位置 `high`。
2. 计算中间位置 `mid = (low + high) // 2`。
3. 比较中间元素与目标值：
- 如果中间元素等于目标值，则返回该位置；
- 如果中间元素大于目标值，则在左半部分继续查找（即 `high = mid - 1`）；
- 如果中间元素小于目标值，则在右半部分继续查找（即 `low = mid + 1`）。
4. 重复上述步骤，直到找到目标值或查找区间为空。
折半查找优缺点总结
| 项目 | 内容 |
| 优点 | 1. 时间效率高，适合大数据量 2. 实现简单，逻辑清晰 3. 适用于静态数据集合 |
| 缺点 | 1. 必须依赖有序序列 2. 插入和删除操作成本较高 3. 不适合频繁更新的数据集 |
| 适用场景 | 1. 数据量大且固定不变 2. 需要频繁查询的场合 3. 存储结构支持随机访问 |
示例说明（以升序数组为例）
假设有一个有序数组：`[1, 3, 5, 7, 9, 11, 13]`，查找目标值为 `7`。
- 初始 `low = 0`, `high = 6`
- 第一次 `mid = (0 + 6) // 2 = 3`，对应值为 `7`，匹配成功，返回索引 `3`
若目标值为 `8`，则过程如下：
- `low = 0`, `high = 6` → `mid = 3` → 值为 `7` < `8` → `low = 4`
- `low = 4`, `high = 6` → `mid = 5` → 值为 `11` > `8` → `high = 4`
- `low = 4`, `high = 4` → `mid = 4` → 值为 `9` > `8` → `high = 3`，此时 `low > high`，查找失败。
总结
折半查找是一种基于分治策略的高效查找方法，特别适用于有序数据的查找任务。虽然其使用条件较为严格，但在实际应用中仍被广泛采用。掌握其原理与实现方式，有助于提升算法设计与优化能力。
