Die Binäre Suche ist ein Such-Algorithmus, der einen Schlüssel (Suchwert x) in einer aufsteigend sortierten Liste findet.
Schrittfolge des Algorithmus
Das Array wird schrittweise in zwei Hälften geteilt und wiederholt mit dem mittleren Index (A[m]) des jeweiligen Suchbereichs verglichen. Wenn x kleiner ist als A[m] wird der linke und wenn x größer ist als A[m] wird der rechte Bereich eingeschränkt. Wenn x gleich A[m] ist, wurde der Suchwert gefunden.
| mittlerer Index m = ⌊ (left + right) / 2⌋ |
******** Pseudocode binäre Suche *********
def left = 0
def right = A.length-1
while left ≤ right do
m = ⌊(left + right)/2⌋
if A[m] = x then
return m
else if x < A[m] then
right = m - 1
else
left = m + 1
End While
return -1
Komplexität des Algorithmus (Laufzeitanalyse)
Best-Case: O(1), Worst Case: O(log2 n), Average Case: O(log2 n)
Die Komplexität der binären Suche hängt von der Länge der Liste (n) ab. Im besten Fall wäre der Schlüssel gleich der mittlere Index. Dann hätte der Algorithmus die Komplexität O(1) und würde nach dem ersten Schritt terminieren. Die Binäre Suche benötigt bei n Elementen log2 n Vergleiche, unabhängig davon ob der Suchwert in der Liste vorhanden ist oder nicht. Die Komplexität O(log2 n) gilt sowohl für den Average- als auch für den Worst Case.
Beispiel 1:
Binäre Suche nach Schlüssel 30 im Array A
Der Algorithmus sucht binär nach dem Schlüssel 30 im Array A mit den aufsteigend sortieren Zahlen 5, 10, 15, 20, 25, 30, 35, 40, 45 und 50. Solange die Bedingung left ≤ right gilt, berechnet der Algorithmus den mittleren Index m des aktuellen Suchbereichs und vergleicht A[m] mit dem Suchwert x = 30.
Initialisierung
Suchbereich A [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] mit zehn Elementen
Suchwert x = 30
Anfang left = A [0] = 5
Ende right = A [(A.length – 1)] = A [(10 – 1)] = A[9] = 50
erster Schritt
Suchbereich A [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] mit zehn Elementen
mittlerer Index m = ⌊ (left + right) / 2 = ⌊ (0 + 9) / 2 ⌋ = 4
A[m] = A[4] = 25
Vergleich x mit A[m]: 30 > 25, links von A[0] = 5 bis A[m + 1] = A[(4 + 1)] = A[5] = 30 ausgeschlossen
zweiter Schritt
Suchbereich [30, 35, 40, 45, 50] mit fünf Elementen
mittlerer Index m =⌊ (left + right) / 2⌋ = ⌊ (0 + 4) / 2⌋ = 2
A[m] = A[2] = 40
Vergleich x mit A[m]: 30 < 40, rechts ab A[m + 1] = A[3] = 45 ausgeschlossen
dritter Schritt
Suchbereich [30, 35] mit zwei Elementen
mittlerer Index m =⌊ (left + right) / 2⌋ = ⌊ (0 + 1) / 2⌋ = 0
A[m] = A[0] = 30
Vergleich x mit A[m]: 30 = 30, Treffer A[0] = 30
Der Algorithmus terminiert nach drei Schritten, da der Wert 30 gefunden wurde. Das Ergebnis ist 0, der Index des Suchwerts.
******** Pseudocode binäre Suche nach Schlüssel 30 *********
input: A [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
def x = 30
def left = 0
def right = A.length-1
while left ≤ right do
m = ⌊(left + right)/2⌋
if A[m] = x then
return m
else if x < A[m] then
right = m - 1
else
left = m + 1
End While
return -1
Beispiel 2:
Binäre Suche nach Schlüssel 42 im Array A
Der Algorithmus sucht binär nach dem Schlüssel 42 im Array A mit den aufsteigend sortieren Zahlen 5, 10, 15, 20, 25, 30, 35, 40, 45 und 50. Solange die Bedingung left ≤ right gilt, berechnet der Algorithmus den mittleren Index m des aktuellen Suchbereichs und vergleicht A[m] mit dem Suchwert x = 42.
Initialisierung
Suchbereich A [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] mit zehn Elementen
Suchwert x = 42
Anfang left = A[0] = 5
Ende right = A[(A.length – 1)] = A[(10 – 1)] = A [9] = 50
erster Schritt
Suchbereich A [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] mit zehn Elementen
mittlerer Index m = ⌊ (left + right) / 2 = ⌊ (0 + 9) / 2 ⌋ = 4
A[m] = A[4] = 25
Vergleich x mit A[m]: 42 > 25, links von A[0] = 5 bis A[m + 1] = A[(4 + 1)] = A[5] = 30 ausgeschlossen
zweiter Schritt
Suchbereich [30, 35, 40, 45, 50] mit fünf Elementen
mittlerer Index m =⌊ (left + right) / 2⌋ = ⌊ (0 + 4) / 2⌋ = 2
A[m] = A[2] = 40
Vergleich x mit A[m]: 42 > 40, links von A[0] = 30 bis A[m + 1] = A[(2 + 1)] = A[3] = 40 ausgeschlossen
dritter Schritt
Suchbereich [45, 50] mit zwei Elementen
mittlerer Index m =⌊ (left + right) / 2⌋ = ⌊ (0 + 1) / 2⌋ = 0
A[m] = A[0] = 45
Vergleich x mit A[m]: 42 < 45, Abbruchbedingung left ≤ right nicht erfüllt,-1
Der Algorithmus bricht nach drei Schritten ab, da die Bedingung left ≤ right nicht mehr erfüllt ist. Der gesuchte Wert 42 wurde nicht gefunden und der Algorithmus liefert das Ergebnis -1.
******** Pseudocode binäre Suche nach Schlüssel 42 *********
input: A [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
def x = 42
def left = 0
def right = A.length-1
while left ≤ right do
m = ⌊(left + right )/2⌋
if A[m] = x then
return m
else if x < A[m] then
right = m - 1
else
left = m + 1
End While
return -1
Die Kommentarfunktion ist deaktiviert, aber Trackbacks und Dingbacks sind offen.