算法学习

二分查找的时间复杂度

假设找到x我们最多需要的步骤是f(N)。

第一步，我们将A[N]一分为二，根据有序数组的特性，通过比较x与标的元素的大小，知道了x落入其中一个子数组B[N/2]。此时问题就变成了 给定一个包含有N/2个元素的有序数组B[N/2]，我们要使用二分法知道元素x是否存在这个数组中。 此时我们进行了一次对比，那么f(n)可以写成

f(N) = 1 + f(N/2)

重复以上步骤，可以得到

f(N) =  1 + f(N/2)
     =  1 + （1 + f(N/4)）
     =  2 + f(n/4)

以此类推，重复k次之后

f(N) = k + f(N/(2^k))

如果以上步骤重复了m次之后，数组只余一个元素无法再分，计算结束。此时

f(N) = m + f(1) = m + 1

因为数组可以二等分m次，所以元素个数N满足：

N = 2^m
或者
N = 2^m + 1

所以

m = log2(N)