实现二分查找并分析时间复杂度

实现二分查找

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

分析时间复杂度

二分查找算法的时间复杂度是 O(log n)。下面我将解释为什么是这样的。

二分查找算法的基本思想是在一个有序数组中不断地将搜索区间减半。具体来说，算法从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束；如果目标值大于中间元素，则在数组的右半部分继续搜索；如果目标值小于中间元素，则在数组的左半部分继续搜索。

每次比较都会将搜索区间减半，因此我们可以说在最坏的情况下（即目标值不在数组中或者在数组的末端），算法需要执行的步骤数与数组长度 n 的对数成正比。这是因为每次操作减少一半的搜索空间，那么经过 k 次操作后，数组的大小将是原来的 1/2^k。要找出 k，我们设置 n/(2^k) = 1，并解出 k。通过对数运算，我们得到 k = log2(n)。因此算法的时间复杂度是 O(log n)。

举例来说，假设我们有一个包含 1 到 1024（包含）的数组，我们要查找数字 1024。二分查找会经历以下步骤：

1. 比较中间的数（大约 512），1024 大于它，因此我们去右边的子数组里查找。
2. 再取右子数组的中间数（大约 768），1024 仍然大于它，再次去右边的子数组里查找。
3. 这样的过程会持续进行，每次我们都排除了一半的数字，直到最后找到 1024。

在这个例子中，1024 是2的10次幂，所以我们需要10步来找到正确的数字，这符合我们的 O(log n) 时间复杂度分析。