二分查找很簡單，可是對于一個區間長度為n的數組，最大的比較次數為多少呢？

對于標準的二分查找，我們每次從區間[l,r)中取一個值，和中間值mid=(l+r)>>1進行比較，然后將數組分為[l,mid) [mid+1,r)，即每次將區間長度x變為(x-1)>>1。最大比較次數顯然是我們想要查找的數并不在數組中的時候，這樣的話我們需要將區間長度變為0才能結束比較。這樣直接分析有些困難，因此我們不妨換一個思路。

如果區間長度為1，顯然最多比較1次
區間長度為2，最多比較2次（[0,2) -> [0,1) -> [0,0)）
區間長度為3，最多比較2次（[0,3) -> [0,1) [2,3)）
區間長度為4，最多比較3次（[0,4) -> [0,2) -> [0,1)）

因此我們不難得到規律：
如果最多比較x次，則區間長度為2^(x-1) ~ 2^x-1
對于區間長度y，最多比較logy+1次

我們對上述發現的規律進行歸納證明：

假設對于區間長度為2^(k-1) ~ 2^k-1的區間，最多比較k次
則對于區間長度為2^k ~ 2^(k+1)-1的區間，假設區間長度為x
如果區間長度為奇數，那么第一次比較以后左右兩個區間的長度在2^(k-1) ~ 2^k-1之間，加上第一次比較，最多比較k+1次
如果區間長度為偶數，那么第一次比較以后較大的區間為長度為偶數的區間，此區間的長度仍然在2^(k-1) ~ 2^k-1之間，加上第一次比較，最多比較k+1次

綜上對于區間長度為2^(k-1) ~ 2^k-1的區間，最多比較k次（k>=1），即對于區間長度y，最多比較logy+1次