Binärer Suchalgorithmus in Java

1. Übersicht

In diesem Artikel werden die Vorteile einer binären Suche gegenüber einer einfachen linearen Suche behandelt und ihre Implementierung in Java erläutert.

2. Notwendigkeit einer effizienten Suche

Nehmen wir an, wir sind im Weinverkaufsgeschäft tätig und Millionen von Käufern besuchen täglich unsere Anwendung.

Über unsere App kann ein Kunde Artikel mit einem Preis unter n Dollar herausfiltern , eine Flasche aus den Suchergebnissen auswählen und in den Warenkorb legen. Wir haben Millionen von Nutzern, die jede Sekunde nach Weinen mit einem Preislimit suchen. Die Ergebnisse müssen schnell sein.

Im Backend führt unser Algorithmus eine lineare Suche durch die gesamte Weinliste durch und vergleicht das vom Kunden eingegebene Preislimit mit dem Preis jeder Weinflasche in der Liste.

Anschließend werden Artikel zurückgegeben, deren Preis unter oder gleich dem Preislimit liegt. Diese lineare Suche hat eine zeitliche Komplexität von O (n) .

Dies bedeutet, je größer die Anzahl der Weinflaschen in unserem System ist, desto länger dauert es. Die Suchzeit erhöht sich proportional zur Anzahl der neu eingeführten Elemente.

Wenn wir beginnen, Elemente in sortierter Reihenfolge zu speichern und mithilfe der binären Suche nach Elementen zu suchen, können wir eine Komplexität von O (log n) erreichen .

Bei der binären Suche nimmt die von den Suchergebnissen benötigte Zeit natürlich mit der Größe des Datensatzes zu, jedoch nicht proportional.

3. Binäre Suche

Einfach ausgedrückt vergleicht der Algorithmus den Schlüsselwert mit dem mittleren Element des Arrays. Wenn sie ungleich sind, wird die Hälfte, zu der der Schlüssel nicht gehören kann, entfernt, und die Suche nach der verbleibenden Hälfte wird fortgesetzt, bis sie erfolgreich ist.

Denken Sie daran - der Schlüsselaspekt hier ist, dass das Array bereits sortiert ist.

Wenn die Suche endet und die verbleibende Hälfte leer ist, befindet sich der Schlüssel nicht im Array.

3.1. Iterative Impl

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

Die runBinarySearchIterativ- Methode verwendet ein sortiertes Array , einen Schlüssel und die niedrigen und hohen Indizes des sortierten Arrays als Argumente. Wenn die Methode zum ersten Mal ausgeführt wird, ist das Tief , der erste Index des sortierten Arrays, 0, während das Hoch , der letzte Index des sortierten Arrays, gleich seiner Länge - 1 ist.

Die Mitte ist der mittlere Index des sortierten Arrays . Jetzt führt der Algorithmus eine while- Schleife aus, in der der Schlüssel mit dem Array-Wert des mittleren Index des sortierten Arrays verglichen wird .

3.2. Rekursive Impl

Schauen wir uns nun auch eine einfache, rekursive Implementierung an:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

Die runBinarySearchRecursively- Methode akzeptiert ein sortiertes Array , einen Schlüssel sowie die niedrigen und hohen Indizes des sortierten Arrays .

3.3. Mit Arrays. binäre Suche()

int index = Arrays.binarySearch(sortedArray, key); 

Ein sortierterArray und ein int- Schlüssel , die im Array von Ganzzahlen durchsucht werden sollen, werden als Argumente an die binarySearch- Methode der Java Arrays- Klasse übergeben.

3.4. Mit Kollektionen. binäre Suche()

int index = Collections.binarySearch(sortedList, key); 

Eine sortierte Liste und ein ganzzahliger Schlüssel , die in der Liste der ganzzahligen Objekte durchsucht werden sollen, werden als Argumente an die binarySearch- Methode der Java Collections- Klasse übergeben.

3.5. Performance

Ob ein rekursiver oder ein iterativer Ansatz zum Schreiben des Algorithmus verwendet wird, ist meist eine Frage der persönlichen Präferenz. Dennoch sind hier einige Punkte, die wir beachten sollten:

1. Die Rekursion kann aufgrund des Overheads bei der Wartung eines Stapels langsamer sein und beansprucht normalerweise mehr Speicher

2. Rekursion ist nicht stapelfreundlich . Es kann dazu führen , Stackoverflow , wenn große Datenmengen verarbeiten

3. Die Rekursion verleiht dem Code Klarheit, da er im Vergleich zum iterativen Ansatz kürzer ist

Im Idealfall führt eine binäre Suche im Gegensatz zu einer linearen Suche nach großen Werten von n weniger Vergleiche durch. Für kleinere Werte von n könnte die lineare Suche eine bessere Leistung erbringen als eine binäre Suche.

Man sollte wissen, dass diese Analyse theoretisch ist und je nach Kontext variieren kann.

Außerdem benötigt der binäre Suchalgorithmus einen sortierten Datensatz, der auch seine Kosten hat . Wenn wir zum Sortieren der Daten einen Zusammenführungssortieralgorithmus verwenden, wird unserem Code eine zusätzliche Komplexität von n log n hinzugefügt.

Zuerst müssen wir unsere Anforderungen gut analysieren und dann entscheiden, welcher Suchalgorithmus am besten zu unseren Anforderungen passt.

4. Fazit

Dieses Tutorial demonstrierte eine Implementierung eines binären Suchalgorithmus und ein Szenario, in dem es vorzuziehen wäre, ihn anstelle einer linearen Suche zu verwenden.

Den Code für das Tutorial finden Sie auf GitHub.