博客

二分查找算法

二分查找（Binary Search），也叫折半查找，是一种利用区间中点来逼近目标值的搜索算法。它的时间复杂度为O(log n)，是一种高效的搜索算法。

算法原理

二分查找算法的核心思想是，在有序数组中，查找某个元素，每次取中间位置的值与目标值进行比较，根据比较结果舍弃一半的元素，重复以上步骤，直到找到或剩下一个元素为止。

具体思路描述如下：

1. 预处理初始化：定义一个左指针，指向数组第一个位置；定义一个右指针，指向数组最后一个位置；定义一个中间指针mid，指向数组中间位置。
2. 判断mid位置的值是否等于目标值，如果等于，则返回位置索引。
3. 如果mid位置的值大于目标值，则查找范围缩小到左侧的一半，将右指针移动到mid左侧一位位置。
4. 如果mid位置的值小于目标值，则查找范围缩小到右侧的一半，将左指针移动到mid右侧一位位置。
5. 重复以上步骤二至四，直到找到目标值或者左指针大于右指针，此时可以判断查找失败。

示例

假设需要在升序排列的数组 arr 中查找目标值 target，代码如下：

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

例如：

arr = [1, 2, 3, 4, 5, 6, 7, 8]
target = 5
print(binary_search(arr, target))
# 输出：4

以上代码的时间复杂度为O(log n)，是一种高效的搜索算法。

注意事项

二分查找算法要求查找的数组必须是有序的，如果是无序的数组，需要先进行排序后再进行二分查找。

此外，注意在实现过程中需要考虑边界问题。具体来说，当左指针等于右指针时，需要判断该位置是否为目标值。如果不判断，会导致在数组中间查找失败的情况。