Quelle: https://nwm2.net-schulbuch.de/index.phpDruckversion vom 18.05.2024 12:12 Uhr
Startseite Einführungsphase Suchen und Sortieren Binäre Suche
Binäre Suche - Fachinhalte
Unter Suchen versteht man das Wiederauffinden bestimmter Informationsteile aus einer großen Menge gespeicherter Informationen. In einem anderem Abschnitt ist die lineare Suche beschrieben worden.
Eine Verbesserung der Suchstrategie ist dann möglich, wenn die folgenden Bedingungen erfüllt sind:
- Die Datensätze müssen so angeordnet sein, dass die Datensatzschlüssel sortiert vorliegen.
- Es muss ein direkter Zugriff auf jeden Datensatz möglich sein. Das ist gewährleistet, wenn die Datensätze in einem Feld (Array) verwaltet werden.
Beispiel: In den folgenden Datensätzen sind die Lebensdaten bekannter Informatikerinnen und Informatiker angeordnet.
Der Datensatzschlüssel „Geburtsjahr“ ist aufsteigend geordnet. Der Zugriff auf einen Datensatz ist über den „Index“ möglich. Die Nummerierung beginnt mit 0, weil es der Nummerierung von Arrays in Java entspricht.
Beschreibung der Suchstrategie:
Man greift auf den Schlüssel in der Mitte des Feldes zu und vergleicht den Wert mit dem Suchschlüssel.
Stimmen Suchschlüssel und Datensatzschlüssel überein, so ist der gesuchte Datensatz gefunden.
Ist der Suchschlüssel kleiner als der Datensatzschlüssel, so muss der gesuchte Datensatz in der ersten Hälfte des Feldes liegen, sonst liegt der Datensatz in der anderen Hälfte.
Dieses Verfahren wird solange fortgesetzt, bis man den gesuchten Datensatz gefunden hat oder das zu untersuchende Teilfeld nur aus einem Datensatz besteht.
Die Suchstrategie heißt Binäre Suche.
Der Suchprozess kann im Pseudocode wie folgt beschrieben werden:
|
Voraussetzung: Die Schlüssel der Elemente im Feld sind sortiert.
Suche im Feld nach einem Element mit dem Schlüssel k: Solange die Feldlänge des Teilfeldes größer als 0 ist und die Suche nicht beendet ist, wiederhole: Nimm das Element auf der mittleren Position m des Feldes und vergleiche den Schlüssel des Elements mit dem Schlüssel k Wenn der Schlüssel k kleiner ist als der Schlüssel des Elements an der Stelle m, durchsuche die linke Feldhälfte bis zum Element an der Stelle m. Wenn der Schlüssel k größer ist als der Schlüssel des Element an der Stelle m, durchsuche die rechte Feldhälfte ab dem Element an der Stelle m. Wenn der Schlüssel k gleich dem Schlüssel des Elements an der Stelle m ist, beende die Suche.
|
Java-Beispielquellcode für die binäre Suche (iterativ):
public void sucheGeburtsjahr(int pSuchschluessel) {
boolean gefunden = false;
int datensatzschluessel;
int oben = if_feld.length - 1;
int unten = 0;
int mitte = 0;
while (!gefunden && (oben - unten >= 0)) {
mitte = (oben + unten) / 2;
datensatzschluessel = if_feld[mitte].gibGeburtsjahr();
if (pSuchschluessel == datensatzschluessel) {
gefunden = true;
} else {
if (pSuchschluessel < datensatzschluessel) {
oben = mitte - 1;
} else {
unten = mitte + 1;
}
}
}
if (gefunden) {
datenAusgeben(if_feld[mitte]);
} else {
datenAusgeben(null);
}
}
Die Verbesserung der Strategie besteht darin, dass die Anzahl der Vergleiche die notwendig sind, um einen Datensatz zu finden, die bei der binäre Suche in der Regel geringer ist als die Anzahl der Vergleiche bei der linearen Suche.