這篇文章將要涉及的問(wèn)題是：二分查找算法（Binary Search）的時(shí)間復(fù)雜度（Time Complexity）為什么是O(logN)?

初始問(wèn)題：
給定一個(gè)包含有N個(gè)元素的有序數(shù)組A[N]，我們要使用二分法知道元素x是否存在這個(gè)數(shù)組中。

假設(shè)找到x我們最多需要的步驟是f(N)。

第一步，我們將A[N]一分為二，根據(jù)有序數(shù)組的特性，通過(guò)比較x與標(biāo)的元素的大小，知道了x落入其中一個(gè)子數(shù)組B[N/2]。此時(shí)問(wèn)題就變成了
給定一個(gè)包含有N/2個(gè)元素的有序數(shù)組B[N/2]，我們要使用二分法知道元素x是否存在這個(gè)數(shù)組中。
此時(shí)我們進(jìn)行了一次對(duì)比，那么f(n)可以寫(xiě)成

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

重復(fù)以上步驟，可以得到

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

以此類推，重復(fù)k次之后

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

如果以上步驟重復(fù)了m次之后，數(shù)組只余一個(gè)元素?zé)o法再分，計(jì)算結(jié)束。此時(shí)

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

因?yàn)閿?shù)組可以二等分m次，所以元素個(gè)數(shù)N滿足：

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

所以

m = log2(N)

也就是說(shuō)，最多經(jīng)歷log2(N)+1次步驟之后，我們獲得查找的結(jié)果。所以二分查找算法的時(shí)間復(fù)雜度為O(logN)。