Einführung
Du bist auf eine Gruppe von Mathematikerinnen und Mathematikern gestoßen, die auch Singer-Songwriter sind.
Sie haben für jede ihrer Lieblingszahlen ein Lied geschrieben, und wie du dir vorstellen kannst, haben sie viele Lieblingszahlen (zum Beispiel 0 oder 73 oder 6174).
Du bist neugierig und möchtest das Lied zu deiner Lieblingszahl hören, aber bei so vielen Liedern kann es eine Weile dauern, bis du das richtige findest.
Zum Glück haben sie ihre Lieder in einer Playlist organisiert, die nach dem Titel sortiert ist, wobei der Titel einfach die Zahl ist, um die es in dem Lied geht.
Du erkennst, dass du mit einer binären Suche schnell ein Lied findest, wenn du seinen Titel kennst.
Anleitung
Deine Aufgabe ist es, eine binäre Suche zu implementieren.
Eine binäre Suche findet ein Element in einer Liste, indem sie die Liste wiederholt halbiert und nur die Hälfte behält, die das gesuchte Element enthält. So grenzen wir die möglichen Positionen unseres Elements schnell ein, bis wir es gefunden haben oder bis wir alle möglichen Positionen ausgeschlossen haben.
Die binäre Suche funktioniert nur, wenn eine Liste sortiert ist.
Der Algorithmus funktioniert so:
- Finde das mittlere Element einer sortierten Liste und vergleiche es mit dem Element, das wir suchen.
- Ist das mittlere Element unser Element, sind wir fertig!
- Ist das mittlere Element größer als unser Element, können wir dieses Element und alle Elemente danach ausschließen.
- Ist das mittlere Element kleiner als unser Element, können wir dieses Element und alle Elemente davor ausschließen.
- Wurde jedes Element der Liste ausgeschlossen, dann ist das Element nicht in der Liste.
- Ansonsten wiederhole den Vorgang mit dem Teil der Liste, der noch nicht ausgeschlossen wurde.
Hier ist ein Beispiel:
Angenommen, wir suchen die Zahl 23 in der folgenden sortierten Liste: [4, 8, 12, 16, 23, 28, 32].
- Wir beginnen damit, 23 mit dem mittleren Element, 16, zu vergleichen.
- Da 23 größer als 16 ist, können wir die linke Hälfte der Liste ausschließen, sodass
[23, 28, 32] übrig bleibt.
- Dann vergleichen wir 23 mit dem neuen mittleren Element, 28.
- Da 23 kleiner als 28 ist, können wir die rechte Hälfte der Liste ausschließen:
[23].
- Wir haben unser Element gefunden.
