Binary Search

Gebrauch

Der Binary Suchalgorithmus wird benutzt, um die Position eines Elements in einer sortierten Liste zu finden.

Java enthält eine Funktion, mit welcher man einen Binary Search unternehmen kann, Arrays.binarySearch().

Spezifikationen

Der Binary Suchalgorithmus hat eine worst-case Performance von O(log n) und eine best-case Performance von O(1). Seine Durchschnittsperformance beträgt O(log n).

Da er keine zusätzliche Liste benötigt, ist seine space complexity immer O(1).

Funktionsweise

Bei dem Binary Search beginnt man zuerst, den Wert in der Mitte des Arrays zu überprüfen. Falls dieser mit dem gesuchten Wert übereinstimmt, kann man gleich den Index des überprüften Wertes zurückgeben.

Falls dies jedoch nicht der Fall ist, wird überprüft, ob der untersuchte Wert grösser oder kleiner als der Gesuchte ist. Da der Array sortiert ist, weiss man, dass der gesuchte Wert einen kleineren Index hat, falls der überprüfte Wert zu gross ist. Falls er jedoch zu klein ist, ist schlusszufolgern, dass der gesuchte Wert einen grösseren Index hat.

Mit diesen Informationen kann man nun den zu überprüfenden Bereich des Arrays minimieren. Somit untersucht man nach der Verkleinerung des Suchbereiches wieder den Wert in der Mitte des neuen Bereiches. Man verkleinert den Suchbereich so lange, bis der gesuchte Wert gefunden wurde oder bis der minimale Wert grösser ist als der Maximale.

Der minimale Wert wird aufgrund des Algorithmus grösser als der Maximale, falls der Wert nicht in dem Array vorhanden ist.

Beispielcode

Dies ist ein in Python geschriebener Beispielcode:

# arr ist der Array, in dem der Wert val zu suchen ist. Die Funktion gibt den Index des gesuchten Wertes zurück def binarySearch(arr, val): # Der minimale Index l = 0 # Der maximale Index r = len(arr) - 1 # Solange der minimale Wert kleiner oder gleich dem maximalen ist while l <= r: # Der zu untersuchende Index index = (l + r) // 2 # Der untersuchte Wert ist kleiner als der Gesuchte => Der gesuchte Wert hat einen grösseren Index if arr[index] < val: l = index + 1 # Der untersuchte Wert ist grösser als der Gesuchte => Der gesuchte Wert hat einen kleineren Index elif arr[index] > val: r = index - 1 # Der untersuchte Wert entspricht dem Gesuchten else: return index # Der Wert ist nicht in dem Array vorhanden return -1

Dies ist ein in Java geschriebener Beispielcode:

Es können selbstverständlich auch andere Datentypen gebraucht werden.

// arr ist der Array, in dem der Wert val zu suchen ist. Die Funktion gibt den Index des gesuchten Wertes zurück public static int binarySearch(int[] arr, int val) { // Der minimale Index int l = 0; // Der maximale Index int r = arr.length - 1; // Der zu untersuchende Index, er wird nach jeder Iteration der folgen While-Schleife berechnet int index; // Solange der minimale Wert kleiner oder gleich dem maximalen ist while (l <= r) { index = (l + r) / 2; // Der untersuchte Wert ist kleiner als der Gesuchte => Der gesuchte Wert hat einen grösseren Index if (arr[index] < val) { l = index + 1; } // Der untersuchte Wert ist grösser als der Gesuchte => Der gesuchte Wert hat einen kleineren Index else if (arr[index] > val) { r = index - 1; } // Der untersuchte Wert entspricht dem Gesuchten else { return index; } } // Der Wert ist nicht in dem Array vorhanden return -1; }

Animiertes Beispiel

Ändere die Position des Sliders, um den gesuchten Wert zu bestimmen und die Animation zu starten.