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, einen Algorithmus für die binäre Suche zu implementieren.
Ein Algorithmus für die binäre Suche findet ein Element in einer Liste, indem er sie wiederholt halbiert und nur die Hälfte behält, die das gesuchte Element enthält.
Damit können wir die möglichen Positionen des gesuchten Elements schnell eingrenzen, bis wir es finden 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 gesuchten Element.
- Wenn das mittlere Element das gesuchte Element ist, sind wir fertig!
- Wenn das mittlere Element größer als das gesuchte Element ist, können wir dieses Element und alle Elemente danach ausschließen.
- Wenn das mittlere Element kleiner als das gesuchte Element ist, können wir dieses Element und alle Elemente davor ausschließen.
- Wenn jedes Element der Liste ausgeschlossen wurde, ist das gesuchte Element nicht in der Liste.
- Andernfalls 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 vergleichen zuerst 23 mit dem mittleren Element, 16.
- Da 23 größer als 16 ist, können wir die linke Hälfte der Liste ausschließen, sodass nur noch
[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 das gesuchte Element gefunden.
