折半查找，也称为二分查找，是一种在有序数组中查找特定元素的搜索算法。其基本思想是将待查找的区间分成两半，然后根据中间元素与目标值的比较结果，确定目标值在数组的哪一半中，从而缩小查找范围。这个过程重复进行，直到找到目标值或查找区间为空。
以下是折半查找的基本步骤：
1. 确定查找区间的初始范围，通常为整个数组的开始和结束索引，分别记为`low`和`high`。
2. 计算中间索引`mid`，通常使用`(low + high) / 2`的方式，但为了避免整数溢出，可以改用`low + (high low) / 2`。
3. 比较中间索引`mid`对应的数组元素与目标值：
如果相等，则查找成功，返回中间索引`mid`。
如果目标值小于中间元素，则在数组的左半部分继续查找，将`high`设置为`mid 1`。
如果目标值大于中间元素，则在数组的右半部分继续查找，将`low`设置为`mid + 1`。
4. 重复步骤2和3，直到找到目标值或`low`大于`high`，即查找区间为空。
折半查找的时间复杂度为O(log n)，这是因为每次查找都会将查找区间缩小一半。这种算法对于有序数组是非常高效的，但需要额外的空间来存储数组索引。
折半查找只适用于有序数组，如果数组未排序，则需要先对数组进行排序，这会增加额外的开销。
