Wie viele Vergleiche wird die binäre Suche im schlimmsten Fall mit diesem Algorithmus machen?

Question

Hallo dort unten ist der Pseudo-Code für meine binäre Such Umsetzung:

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 

ich gerade fragen, wie die Anzahl der Vergleiche berechnen diese Implementierung im schlimmsten Fall für eine sortierte Array der Größe n machen würde?

Würde die Anzahl der Vergleiche = lg n + 1? oder etwas anderes?

Answer 1

Die Worst-Case ist in diesem Fall, wenn das Element K nicht in A und kleiner als alle Elemente in A. Dann wird in jedem Schritt haben wir zwei Vergleiche: K > A[m] und K < A[m].

Für in jedem Schritt wird das Array in zwei Teile geschnitten, jedes der Größe (n-1)/2, wir haben maximal log_2(n-1) Schritte. Dies führt zu insgesamt 2*log_2(n-1) Vergleichen, die asymptotisch tatsächlich O(log(n)) entsprechen.

Answer 2

Laut Wikipedia-Seite binary search ist die Worst-Case-Leistung dieses Algorithmus O(lg n), die die asymptotische Anzahl der erforderlichen Vergleiche misst. Die tatsächliche Worst-Case-Anzahl von Vergleichen wäre 2*lg(n-1), wie in @ Hielsnoppe's Antwort gezeigt wurde.

Der Pseudo-Code in der Frage stellt die typische Implementierung einer binären Suche, so dass die erwartete Leistung Komplexität hält für ein Array (oder Vektor) der Größe n:

• Best case Leistung: O(1)
• Durchschnitt Fall Leistung: O(lg n)
• Worst-Case-Leistung: O(lg n)

Bei näherer Betrachtung gibt es zwei Probleme mit dem Pseudo-Code in der Frage:

• Die Linie: if K > A[m] then return l ← m+1 soll if K > A[m] then l ← m+1 lesen. Sie können nicht zurück
• Die Zeile: m ← floor((l+r)/2) kann einen Überlauf verursachen, wenn die Nummern groß genug sind, wenn Sie mit Ganzzahlen fester Größe arbeiten. Die richtige Syntax hängt von der tatsächlichen Programmiersprache ab, die Sie verwenden, aber etwas dabei wird das Problem beheben: m ← (l + r) >>> 1, wobei >>> der vorzeichenlose Rechtsverschiebeoperator ist. Lesen Sie mehr über das Problem in here.

Answer 3

eine sehr geringe Korrektur hielsnoppe's answer:

In einem n -Glied array (n > 0), das Element zu vergleichen, ist bei Index m = floor((n-1)/2). So gibt es drei Möglichkeiten

1. A[m] < K, dann nach einem Vergleich geht die Suche in einem n-1-m = ceiling((n-1)/2) -elementigen Array.Die Suche wird dann nach zwei Vergleichen in einem m -Element-Array fortgesetzt.
2. A[m] == K, dann sind wir nach zwei Vergleichen fertig.

Wenn wir also den maximalen (worst-case) Anzahl von Vergleichen für eine Suche in einem n -elementigen Array von C(n) bezeichnen, haben wir

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

Für ungerade n = 2k+1, Boden und Decke sind identisch, so offenbar die letztere das Maximum ist,

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

und sogar n = 2k finden wir

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

Für n = 2, dass beschließt zu C(2) = 1 + C(1) = 1 + 2 = 3, für alle größeren sogar n ist die maximale 2 + C(k-1), da für n >= 1 wir C(n) <= C(n+1) <= C(n) + 1 haben.

die Rekursion für die ersten paar n auswerten, finden wir

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 

So durch Induktion wir

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) 

oder

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

Dies ist eine exakte Obergrenze beweisen.