二分的时间复杂度计算

二分查找的时间复杂度求导过程

1.设T(n)为求出规模为n问题的时间复杂度
2.O(1)表示用一次将规模为 n 的问题化为规模为 n / 2 的问题

那么我们有：

T(n) = T(n / 2) + O(1) * 1
     = T(n / 4) + O(1) * 2
     = T(n / 8) + O(1) * 3
     = T(n / 16) + O(1) * 4

设O(1)的系数是 x, 则可知 x 为将 T(n) 转化为 T(1) 的次数；

则：

  n(1 / 2) ^ x = 1
  (1 / 2) ^ x = 1 / n
  log(2)(n) = x

所以:

  T(n) = T(1) + O(1) * log(2)(n)
  T(n) = T(1) + O(log(2)(n))

因为T(1)在此问题中表示获取值，即T(1) = O(1)

  T(n) = O(1 + log(2)(n))

只取高次项，所以

  T(n) = O(log n)

因为T(n)表示的是求解规模为n问题的时间复杂度

所以二分查找的时间复杂度为O(log n)