Binäre Suche in Java: Funktionsweise und Beispiele

Die binäre Suche ist einer der effizientesten Algorithmen, um ein Element in einem geordneten Array zu finden. Es basiert auf dem Prinzip, die Aufgabe in zwei Hälften zu teilen, sodass Sie das gesuchte Element anhand einer minimalen Anzahl von Vergleichen finden können.

Das Prinzip der binären Suche ist wie folgt. Zunächst müssen wir die Suchgrenzen definieren - die Anfangs- und Endindizes des Arrays. Dann vergleichen wir den gewünschten Wert mit dem Mittelelement des Arrays. Wenn das Element, nach dem wir suchen, gleich dem mittleren Element ist, ist die Suche beendet. Wenn das gesuchte Element kleiner als das mittlere Element ist, kann es sich nur in der linken Hälfte des Arrays befinden. Andernfalls, wenn das gesuchte Element größer als das mittlere Element ist, kann es sich nur in der rechten Hälfte des Arrays befinden. Daher teilen wir das Array nacheinander in zwei Hälften und verengen die Suchgrenzen, bis wir das gesuchte Element gefunden haben oder bis ein Element übrig ist.

Beispiel für die Implementierung einer binären Suche in Java:

public static int binarySearch(int[] array, int key) else if (array[mid] < key) else >return -1;>

In diesem Beispiel implementieren wir eine Methode binarySearch, das ein geordnetes Array und das gesuchte Element akzeptiert. Die Methode führt eine binäre Suche durch und gibt den Index des gesuchten Elements zurück, wenn es gefunden wird, oder -1, wenn das Element nicht gefunden wird. Indem wir das Array in zwei Hälften teilen, indem wir das Mittelelement mit dem Schlüssel vergleichen, finden wir effektiv das gesuchte Element, indem wir O(log n) -Operationen verwenden.

Das Prinzip der binären Suche in Java

Die Idee der binären Suche ist wie folgt:

1. Gibt ein geordnetes Datenarray an, in dem gesucht werden soll.
2. Es werden zwei Zeiger festgelegt, das Start- und das Endelement des Arrays.
3. Das mittlere Element des Arrays wird berechnet und mit dem gewünschten Wert verglichen.
4. Wenn das mittlere Element gleich dem gewünschten Wert ist, ist die Suche erfolgreich.
5. Wenn das mittlere Element größer als der gesuchte Wert ist, wird der Suchbereich auf die linke Hälfte des Arrays verengt.
6. Wenn das mittlere Element kleiner als der gesuchte Wert ist, wird der Suchbereich auf die rechte Hälfte des Arrays verengt.
7. Der Vorgang wird wiederholt, bis das Array vollständig untersucht wurde oder das gesuchte Element gefunden wurde.

Die binäre Suche in Java hat eine Zeitkomplexität von O(log n), wobei n die Anzahl der Elemente im Array ist. Dadurch können Sie effizient mit großen Datenmengen arbeiten.

Ein Beispiel für die Implementierung einer binären Suche in Java könnte folgendermaßen aussehen:

public class BinarySearch return -1; // Искомый элемент не найден>>

In diesem Beispiel nimmt die BinarySearch-Methode ein geordnetes array und das gesuchte target-Element an. Der Algorithmus führt eine binäre Suche durch und gibt den Index des gesuchten Elements zurück, wenn es gefunden wurde, oder -1, wenn das Element nicht gefunden wurde.

Um die binäre Suche zu verwenden, rufen Sie einfach die BinarySearch-Methode auf und übergeben Sie die erforderlichen Parameter an sie.

Was ist eine binäre Suche?

Der binäre Suchalgorithmus funktioniert wie folgt:

1. Das mittlere Element des Arrays befindet sich.
2. Wenn es dem gesuchten Element entspricht, wird die Suche beendet.
3. Wenn es größer ist als das gesuchte Element, wird die Suche in der linken Hälfte des Arrays fortgesetzt.
4. Wenn es kleiner als das gesuchte Element ist, wird die Suche in der rechten Hälfte des Arrays fortgesetzt.
5. Die Schritte 1 bis 4 werden wiederholt, bis das gesuchte Element gefunden wird.

Mit der binären Suche können Sie Elemente wesentlich schneller finden als bei der linearen Suche, insbesondere in großen Datenmengen. Dieser Algorithmus ist besonders nützlich, wenn Elemente in einer geordneten Reihenfolge angeordnet sind, da er bei jeder Iteration die Hälfte des Arrays ausschließen kann.

Das Grundprinzip der binären Suche

Die Grundidee der binären Suche ist wie folgt:

1. Definieren Sie den Anfang und das Ende des Suchintervalls im Array.
2. Finde das mittlere Element (der Index der Anfangs- und Endsumme geteilt durch zwei).
3. Vergleichen Sie den gewünschten Wert mit dem aktuellen Durchschnittswert.
4. Wenn der gesuchte Wert gleich dem aktuellen mittleren Element ist, ist die Suche abgeschlossen.
5. Wenn der gewünschte Wert kleiner als das aktuelle Mittelelement ist, wiederholen Sie die Schritte 1 bis 4 für die linke Hälfte des Arrays.
6. Wenn der gewünschte Wert größer als das aktuelle Mittelelement ist, wiederholen Sie die Schritte 1 bis 4 für die rechte Hälfte des Arrays.
7. Wiederholen Sie die Schritte 1 bis 6, bis der gesuchte Wert gefunden wurde oder das Suchintervall auf Null verengt ist.

Die binäre Suche hat eine logarithmische Laufzeitkomplexität, was sie bei der Arbeit mit großen sortierten Arrays effizient macht.

Beispielcode für binäre Suche in Java:

public static int binarySearch(int[] array, int target) else if (array[mid] < target) else >return -1;>

In diesem Beispiel nimmt die BinarySearch-Funktion das sortierte Array und den gewünschten Wert an. Sie verengt das Suchintervall mithilfe einer Schleife, bis der gesuchte Wert gefunden wird oder das Intervall leer ist. Wenn ein Wert in einem Array gefunden wird, gibt die Funktion seinen Index zurück. Andernfalls wird -1 zurückgegeben.

Vorteile der Verwendung der binären Suche

1. Schneller Betrieb: Die binäre Suche hat eine logarithmische Komplexität in Bezug auf die Laufzeit, was bedeutet, dass sie selbst bei sehr großen Datenmengen sehr schnell funktioniert. Dies macht es besonders nützlich für die Suche in großen Datenbanken oder Anwendungen, die einen schnellen Datenzugriff erfordern.
2. Speicher sparen: Die binäre Suche erfordert keine zusätzliche Speicherverwendung zum Speichern von Zwischenergebnissen, da sie auf der Grundlage eines Vergleichs der Werte der Elemente im Array ausgeführt wird. Dies spart Ressourcen und erhöht die Effizienz des Programms.
3. Garantierte Korrektheit: Die binäre Suche ist eine algorithmisch korrekte Methode, um ein Element in einem Array zu finden. Es wird garantiert das gewünschte Element finden, wenn es im Array vorhanden ist, oder es wird das entsprechende Ergebnis zurückgeben, wenn das Element fehlt. Dies ermöglicht es Entwicklern, sicher zu sein, dass das Programm ordnungsgemäß funktioniert.

Die Verwendung der binären Suche kann die Leistung von Such- und Datenverarbeitungsalgorithmen erheblich verbessern. Beachten Sie jedoch, dass die binäre Suche nur für geordnete Daten möglich ist, daher müssen Sie das Array oder die Liste der Elemente vorsortieren.

Implementierung der binären Suche in Java

Um die binäre Suche in Java zu implementieren, verwenden wir den folgenden Algorithmus:

1. Zuerst müssen Sie das Array sortieren, in dem die Suche durchgeführt werden soll. Die binäre Suche funktioniert nur mit sortierten Daten.
2. Dann definieren wir den Anfangs- und Endindex des Arrays.
3. Wir berechnen den durchschnittlichen Index des Arrays.
4. Vergleichen Sie den Wert des mittleren Elements mit dem gewünschten Wert. Wenn sie übereinstimmen, geben wir den Index zurück.
5. Wenn der gesuchte Wert kleiner als das mittlere Element ist, setzen Sie die Suche in der linken Hälfte des Arrays fort und setzen den neuen Wert des Zielindexes ein.
6. Wenn der gesuchte Wert größer als das mittlere Element ist, setzen Sie die Suche in der rechten Hälfte des Arrays fort und setzen den neuen Wert des Anfangsindexes ein.
7. Wiederholen Sie die Schritte 3 bis 6, bis wir das gesuchte Element gefunden haben oder feststellen, dass es nicht im Array ist.
8. Wenn wir das gesuchte Element im Ergebnis der Suche nicht finden, geben wir -1 oder einen anderen Wert zurück, der angibt, dass es fehlt.

Beispielcode für die Implementierung einer binären Suche in Java:

public static int binarySearch(int[] arr, int key) if (arr[mid] < key) else >return -1;>

Diese Methode akzeptiert das sortierte Array und den Suchschlüssel als Parameter und gibt den Index des gefundenen Elements oder -1 zurück, wenn das Element nicht gefunden wird.

Beispiele für die Verwendung der binären Suche

Beispiel 1:

int[] array = ;int target = 6;int result = binarySearch(array, target);if (result != -1) else

In diesem Beispiel suchen wir nach einem Element mit dem Wert 6 in einem sortierten Array . Das Ergebnis der Programmausführung ist die Meldung "Element 6 an Position 2 gefunden".

Beispiel 2:

String[] array = ;String target = "cherry";int result = binarySearch(array, target);if (result != -1) else

In diesem Beispiel suchen wir nach dem Element "cherry" in einem sortierten Array von Strings . Das Ergebnis der Programmausführung ist die Meldung "Cherry-Element an Position 2 gefunden".

Beispiel 3:

List list = new ArrayList<>(Arrays.asList(1, 3, 5, 7, 9));int target = 8;int result = binarySearch(list, target);if (result != -1) else

In diesem Beispiel verwenden wir die binäre Suche, um nach einem Element mit dem Wert 8 in einer Liste von Zahlen zu suchen [13579]. Das Ergebnis der Ausführung des Programms lautet die Meldung "Element 8 wurde nicht gefunden".

Dies sind nur einige Beispiele für die Verwendung der binären Suche in Java. Die binäre Suche kann ein nützlicher Algorithmus sein, wenn Sie mit sortierten Arrays oder Datenlisten arbeiten, sodass Sie effektiv nach den gewünschten Elementen suchen können.

Binäre Suche in sortierten Arrays

Das Prinzip der binären Suche ist wie folgt:

1. Der Wert wird von der mittleren Position des Arrays übernommen.
2. Wenn es gleich dem Zielwert ist, wird die Suche beendet und der Index dieses Werts wird zurückgegeben.
3. Wenn der Wert kleiner als der Zielwert ist, wird die Suche in der rechten Hälfte des Arrays durchgeführt, andernfalls in der linken Hälfte.
4. Der Prozess wird wiederholt, bis der Wert gefunden wurde oder das Array vollständig untersucht wurde.

Die binäre Suche ermöglicht es Ihnen, Werte in einem Array viel schneller zu finden als die lineare Suche, geht jedoch davon aus, dass das Array bereits sortiert ist. Wenn es nicht sortiert ist, müssen Sie es zuerst mit einem anderen Algorithmus sortieren, z. B. einer Merge-Sortierung oder einer Schnellsortierung.

Beispiel für die Implementierung einer binären Suche in Java:

public static int binarySearch(int[] array, int target) else if (array[mid] < target) else >return -1;>

In diesem Beispiel akzeptiert die BinarySearch-Funktion ein sortierbares array und einen Zielwert von target . Es gibt den Index des gefundenen Werts oder -1 zurück, wenn kein Wert gefunden wurde.

Bei einer binären Suche trennen wir das Array und vergleichen den Zielwert mit dem Element in der Mitte des Arrays. Wenn sie nicht übereinstimmen, setzen wir die Suche in der rechten oder linken Hälfte des Arrays fort, verengen den Suchbereich und wiederholen den Vorgang, bis ein Wert gefunden wird oder der Suchbereich leer ist.

Daher ermöglicht die binäre Suche das Finden von Werten in sortierten Arrays viel effizienter als die lineare Suche und hat eine logarithmische Laufzeitkomplexität von O(log n).

Binäre Suche in Bäumen

Die binäre Suche im Baum erfolgt wie folgt. In jedem Schritt wird der gesuchte Wert mit dem Wert des aktuellen Knotens verglichen. Wenn sie gleich sind, wird das Element gefunden. Wenn der gesuchte Wert kleiner als der aktuelle Knotenwert ist, wird die Suche im linken Teilbaum fortgesetzt. Wenn der gesuchte Wert größer ist als der Wert des aktuellen Knotens, wird die Suche im rechten Teilbaum fortgesetzt. Der Prozess wird fortgesetzt, bis das gesuchte Element gefunden wurde oder das Ende des Baums erreicht ist.

Die binäre Suche in Bäumen hat eine ähnliche Komplexität wie die binäre Suche im Array – O(log n), wobei n die Anzahl der Elemente in einem Baum oder Array ist. Die binäre Baumsuche kann jedoch bei Knoten mit einer großen Anzahl von Kindern effizienter sein, da sie mehr als die Hälfte der Knoten bei jedem Suchschritt ausschließen kann.

Ein Beispiel:

class TreeNode >public class BinaryTree else if (value < current.value) else >return false;>>

In diesem Beispiel wird die Implementierung einer binären Suche in einem Binärbaum veranschaulicht. Die contains-Methode überprüft, ob ein Element mit dem angegebenen Wert in der Struktur vorhanden ist. Es beginnt, die Werte des gesuchten Elements mit den Werten der Baumknoten zu vergleichen, bewegt sich je nach Ergebnis des Vergleichs nach rechts oder links und fährt fort, bis das gesuchte Element gefunden wird oder das Ende des Baumes erreicht ist.

Die binäre Baumsuche ist ein leistungsfähiger Algorithmus, der verwendet werden kann, um Elemente in baumbasierten Datenstrukturen effektiv zu finden.

Binäre Suche in Graphen

In Graphen kann eine binäre Suche verwendet werden, um den kürzesten Pfad zwischen zwei Stützpunkten zu finden oder um zu überprüfen, ob eine Kante zwischen zwei Stützpunkten vorhanden ist. Dazu muss das Diagramm als Adjazenzliste dargestellt und sortiert werden, damit die binäre Suche angewendet werden kann.

Das Prinzip der binären Suche in Graphen ähnelt dem Prinzip der binären Suche in geordneten Datenlisten. Der Algorithmus vergleicht den gewünschten Wert mit dem mittleren Element der Adjazenzliste. Wenn der Wert übereinstimmt, wurde das Element gefunden. Wenn der Wert kleiner ist, wird die Suche in der linken Hälfte der Adjazenzliste fortgesetzt. Wenn der Wert größer ist, wird die Suche in der rechten Hälfte der Adjazenzliste fortgesetzt. Dies wird fortgesetzt, bis das gesuchte Element gefunden wird oder die Suche das Ende der Adjazenzliste erreicht.

Die binäre Suche in Graphen kann bei der Lösung verschiedener Aufgaben im Zusammenhang mit der Suche nach Pfaden, der Überprüfung der Beziehungen zwischen Stützpunkten und der Optimierung von Algorithmen in Graphen nützlich sein. Um es anzuwenden, muss das Diagramm jedoch vorsortiert und als Adjazenzliste dargestellt werden.

Binäre Suche in Strings

Führen Sie die folgenden Schritte aus, um eine binäre Suche in Strings durchzuführen:

1. Ordnen Sie die Zeilen an, bevor Sie mit der Suche beginnen. Sie können dies tun, indem Sie die Liste der Zeilen alphabetisch oder nach einem anderen festgelegten Kriterium sortieren.
2. Finden Sie die Mitte einer geordneten Liste von Zeilen.
3. Vergleichen Sie die gesuchte Zeichenfolge mit dem Element in der Mitte der Liste.
4. Wenn die Zeilen übereinstimmen, wurde das Element gefunden.
5. Wenn die gesuchte Zeichenfolge kleiner als ein Element in der Mitte der Liste ist, wird eine binäre Suche für die linke Hälfte der Liste durchgeführt.
6. Wenn die gesuchte Zeichenfolge größer ist als ein Element in der Mitte der Liste, wird eine binäre Suche für die rechte Hälfte der Liste durchgeführt.
7. Wiederholen Sie die Schritte 2 bis 6, bis die gesuchte Zeile gefunden wird oder die Liste erschöpft ist.

Die binäre Suche in Strings kann beispielsweise nützlich sein, um ein bestimmtes Wort in einem Wörterbuch zu finden oder einen bestimmten Namen in einer sortierten Namensliste zu finden.

Beispielcode für die binäre Suche in Strings in Java:

public static int binarySearch(String[] arr, String x) if (result < 0) else >return -1;>

In diesem Beispiel verwenden wir die compareTo-Methode aus der String-Klasse, um die Zeichenfolge x mit einem Element in der Mitte der Liste zu vergleichen. Der Code gibt den Index des gefundenen Elements oder -1 zurück, wenn das Element nicht gefunden wurde.

Daher ist die binäre Suche in Strings eine effektive Möglichkeit, das gewünschte Element in einer geordneten Liste von Strings zu finden, was in verschiedenen Programmiersituationen nützlich sein kann.