【数据结构折半查找】在数据结构中，折半查找（Binary Search）是一种高效的查找算法，适用于已排序的线性表。它通过不断将查找区间一分为二，逐步缩小可能的范围，从而快速定位目标元素。相比顺序查找，折半查找的时间复杂度更低，效率更高。
折半查找的基本思想
折半查找的核心思想是：在有序数组中，每次比较中间元素与目标值，根据比较结果决定继续在左半部分或右半部分查找。如果中间元素等于目标值，则查找成功；若小于目标值，则在右半部分继续查找；若大于目标值，则在左半部分查找。
该方法要求被查找的数据必须是有序排列的，否则无法使用折半查找。
折半查找的步骤
1. 确定查找区间的起始位置 `low` 和结束位置 `high`。
2. 计算中间位置 `mid = (low + high) // 2`。
3. 比较 `arr[mid]` 与目标值 `target`：
- 如果相等，返回 `mid`；
- 如果 `arr[mid] < target`，则在右半部分查找，即 `low = mid + 1`；
- 如果 `arr[mid] > target`，则在左半部分查找，即 `high = mid - 1`。
4. 重复上述步骤，直到找到目标值或查找区间为空。
折半查找的特点
| 特点 | 描述 |
| 时间复杂度 | O(log₂n) |
| 空间复杂度 | O(1)（非递归实现） |
| 适用条件 | 必须是有序数组 |
| 查找效率 | 高于顺序查找 |
| 是否破坏原数组 | 否 |
示例代码（Python）
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
```
折半查找的应用场景
- 在数据库中对有序索引进行高效查询；
- 在程序中处理大量有序数据时提升查找效率；
- 在算法竞赛中用于优化时间复杂度。
总结
折半查找是一种基于分治策略的高效查找算法，适用于已排序的数据集合。其核心在于不断缩小查找范围，以最短路径找到目标元素。虽然其应用范围受到数据有序性的限制，但在实际开发中仍具有重要价值。掌握折半查找的原理和实现方式，有助于提高编程效率与算法理解能力。