这篇文章将要涉及的问题是：二分查找算法（Binary Search）的时间复杂度（Time Complexity）为什么是O(logN)?
初始问题：
给定一个包含有N个元素的有序数组A[N]，我们要使用二分法知道元素x是否存在这个数组中。
假设找到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)
也就是说，最多经历log2(N)+1次步骤之后，我们获得查找的结果。所以二分查找算法的时间复杂度为O(logN)。
