Die binäre Suche ist ein effizienter Suchalgorithmus, der auf einem sortierten Array basiert. Sie funktioniert, indem das Array in der Mitte geteilt wird, und prüft, ob das gesuchte Element links oder rechts vom Mittelpunkt liegt. Dieser Vorgang wird wiederholt, bis das Element gefunden wird oder die Liste aufgebraucht ist.
Die binäre Suche funktioniert nur mit sortierten Daten und ist wesentlich schneller als das sequentielle Suchen, insbesondere bei großen Datenmengen.
Vergleichszahlen bei erfolgreicher Suche:
log2(n)log2(n)Vergleichszahlen bei erfolgloser Suche:
log2(n) Vergleiche notwendigO(log n)
Die Laufzeitkomplexität der binären Suche beträgt im schlimmsten Fall O(log n), was sie für große Datenmengen deutlich schneller macht als die lineare Suche.
Gegeben: Liste [4, 8, 15, 16, 23, 42]
Gesucht: 23
Durchlauf:
1. Erster Schritt:
Die Liste hat 6 Elemente. Wir starten mit dem gesamten Bereich von Index 0 bis 5.
Die Mitte liegt bei Position (0 + 5) / 2 = 2,5. Wir runden ab und erhalten Index 2, also das Element 15.
Vergleich: 23 > 15 → Gesuchte Zahl liegt rechts von der Mitte.
⬇️ Wir ignorieren den linken Teil und betrachten nun nur noch: [16, 23, 42]
2. Zweiter Schritt:
Neuer Bereich: Index 3 bis 5.
Neue Mitte: (3 + 5) / 2 = 4 → Element 23 an Position 4.
Vergleich: 23 = 23 → Treffer!
✅ Ergebnis: 23 gefunden!
Die Mitte einer Liste wird durch den Mittelwert der aktuellen Start- und Endposition (Index) berechnet. Beispiel: Bei einer Liste mit 6 Elementen (Index 0 bis 5) gilt:
(0 + 5) / 2 = 2,5 → abgerundet ergibt das Index 2. Das ist das Element 15.
In der binären Suche wird dann geprüft, ob das gesuchte Element kleiner, gleich oder größer als dieses mittlere Element ist. So kann man jeweils eine Hälfte der Liste ausschließen und spart dadurch viele Vergleiche.
Wichtig: Die Liste muss sortiert sein! Sonst funktioniert die binäre Suche nicht korrekt.
Hinweis: Die Lösung Ihrer Aufgabe muss in Moodle hochgeladen werden.