二進制搜索在最壞的情況下會使用這種算法進行多少次比較？

Question

您好以下是我的二進制搜索實現的僞代碼：

Input: (A[0...n-1], K) 
begin 
    l ← 0; r ← n-1 
    while l ≤ r do 
     m ← floor((l+r)/2) 
     if K > A[m] then l ← m+1 
     else if K < A[m] then r ← m-1 else return m 
     end if 
    end while 
    return -1 // key not found 
end 

我只是想知道如何計算這個實施將使得在最壞的情況下大小爲n的有序數組比較的次數？

比較次數= lg n + 1？或不同的東西？

Answer 1

的最壞情況在這種情況下，如果該元件K不存在於A和比A.所有元素然後我們在每個步驟兩次比較小：K > A[m]和K < A[m]。

對於每個步驟中的數組被切割成兩部分，每個的大小爲(n-1)/2，我們有最多log_2(n-1)步驟。

這導致總共2*log_2(n-1)比較，其漸近地確實等於O(log(n))。

Answer 2

根據binary search上的維基百科頁面，該算法的最壞情況性能爲O(lg n)，它測量所需比較的漸進數量。 實際最壞情況下的比較次數是2*lg(n-1)，正如@ hielsnoppe的答案所指出的那樣。

在問題的僞碼錶示的二進制搜索的典型的實施方式，所以所期望的性能的複雜性保持爲尺寸n的陣列（或向量）：

• 最佳情況下的性能：O(1)
• 平均情況下的性能：O(lg n)
• 最壞情況下的性能：O(lg n)

在仔細檢查，有兩個問題，在這個問題的僞代碼：

• 行：if K > A[m] then return l ← m+1應該讀if K > A[m] then l ← m+1。您還不能返回
• 如果使用固定大小的整數處理的數字足夠大，則可能會導致溢出：m ← floor((l+r)/2)。正確的語法根據您使用的實際編程語言而有所不同，但沿着這一點可以解決問題：m ← (l + r) >>> 1，其中>>>是無符號的右移運算符。詳細瞭解here中的問題。

Answer 3

一個很小的校正hielsnoppe's answer：

在n - 元素陣列（n > 0），比較元件是在索引m = floor((n-1)/2)。因此，有三種可能性

1. A[m] < K，那麼一個比較後，搜索在n-1-m = ceiling((n-1)/2) - 元素陣列繼續。
2. A[m] > K，然後在兩次比較後，搜索繼續到m -element數組中。
3. A[m] == K，然後我們完成兩次比較後。

因此，如果我們表示的最大（最壞情況）的比較的數目用於在n - 元素陣列的搜索通過C(n)，我們有

C(0) = 0 
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0 

對於奇數n = 2k+1，地板和天花板的相同的，所以最大顯然是後者，

C(2k+1) = 2 + C(k) 

和甚至n = 2k，我們發現

C(2k) = max { 1 + C(k), 2 + C(k-1) }. 

對於n = 2，解析爲C(2) = 1 + C(1) = 1 + 2 = 3，所有更大n，最高2 + C(k-1)，由於n >= 1我們有C(n) <= C(n+1) <= C(n) + 1。

評估前幾n遞歸，我們發現

C(0) = 0 
C(1) = 2 
C(2) = 3 
C(3) = C(4) = 4 
C(5) = C(6) = 5 
C(7) = C(8) = C(9) = C(10) = 6 
C(11) = ... = C(14) = 7 
C(15) = ... = C(22) = 8 
C(23) = ... = C(30) = 9 

因此，通過感應證明

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and 
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1) 

或

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))). 

這是一個確切的上限。