Binary Search

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到所需的元素。这种搜索算法每一次比较都使搜索范围缩小一半，因此效率较高。

以下是二分查找算法的基本步骤：

1. 确定搜索范围：初始化两个指针，一个指向数组的起始位置 low，另一个指向数组的结束位置 high。

2. 计算中间位置：计算中间索引 mid，通常是 (low + high) / 2，取整结果。

3. 比较中间元素：将数组中间位置的元素与目标值进行比较。

4. 确定搜索方向：

   • 如果 array[mid] 等于目标值，搜索成功，返回 mid。
   • 如果 array[mid] 大于目标值，说明目标值在数组的左半部分，更新 high 为 mid - 1。
   • 如果 array[mid] 小于目标值，说明目标值在数组的右半部分，更新 low 为 mid + 1。

5. 重复过程：继续以上步骤，直到找到目标值，或者 low 大于 high，表示目标值不在数组中。

6. 结束条件：如果 low 大于 high，则表示目标值不在数组中，搜索结束，返回一个表示未找到的值（通常是 -1）。

以下是二分查找的伪代码示例：

function binarySearch(array, target, low, high)
    while low <= high
        mid := low + (high - low) / 2
        if array[mid] === target
            return mid
        else if array[mid] < target
            low := mid + 1
        else
            high := mid - 1
    return -1 // 目标值未找到

二分查找算法的时间复杂度是 O(log n)，其中 n 是数组的长度。这种算法的效率远高于线性搜索，特别是对于大型数据集。然而，二分查找要求数组是有序的，如果数组未排序，则需要先排序，这会消耗额外的时间。