【数据结构折半查找】在数据结构中，折半查找（Binary Search）是一种高效的查找算法，适用于有序数组。与线性查找相比，折半查找通过不断将查找区间对半分割，从而显著减少查找次数，提高效率。
一、折半查找的基本思想
折半查找的核心思想是：在有序数组中，每次将查找范围分成两半，比较中间元素与目标值的大小，根据比较结果决定继续在左半部分或右半部分查找。这一过程重复进行，直到找到目标元素或确定其不存在。
二、折半查找的适用条件
| 条件 | 说明 |
| 数组必须有序 | 折半查找要求数据按升序或降序排列 |
| 支持随机访问 | 必须能够快速访问任意位置的元素（如数组） |
| 数据量较大 | 对于小数据集，线性查找可能更简单高效 |
三、折半查找的步骤
1. 初始化：设置两个指针 `low` 和 `high`，分别指向数组的起始和结束位置。
2. 循环查找：
- 计算中间位置 `mid = (low + high) / 2`
- 比较 `arr[mid]` 与目标值 `target`：
- 如果 `arr[mid] == target`，则查找成功，返回 `mid`
- 如果 `arr[mid] < target`，则在右半部分查找，更新 `low = mid + 1`
- 如果 `arr[mid] > target`，则在左半部分查找，更新 `high = mid - 1`
3. 终止条件：当 `low > high` 时，表示查找失败。
四、折半查找的时间复杂度
| 时间复杂度 | 说明 |
| 最好情况 | O(1)（第一次就找到目标） |
| 最坏情况 | O(log n)（每次都将查找区间减半） |
| 平均情况 | O(log n) |
五、折半查找的优缺点
| 优点 | 缺点 |
| 查找效率高，适合大数据量 | 要求数据必须有序 |
| 算法结构清晰，易于实现 | 不适用于链表等不支持随机访问的数据结构 |
| 运行时间稳定，无明显波动 | 需要额外空间存储排序后的数据（若原数据无序） |
六、折半查找示例（C语言）
```c
int binarySearch(int arr[], int n, int target) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1; // 未找到
}
```
七、总结
折半查找是一种基于分治策略的高效查找算法，适用于有序数组。它通过不断缩小查找范围来提升查找效率，在实际应用中具有广泛的使用价值。虽然其对数据的有序性有要求，但一旦满足条件，其性能远优于线性查找。在编程实践中，合理选择查找算法可以显著提升程序运行效率。
