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.
Einschränkungen
Rust stellt in seiner Standardbibliothek bereits eine
Binärsuchfunktion
bereit. Für diese Übung solltest du diese Funktion nicht verwenden, sondern nur andere
grundlegende Werkzeuge.
Für Bonuspunkte
Hast du die Tests zum Laufen gebracht und den Code sauber bekommen? Wenn du möchtest,
gibt es noch ein paar zusätzliche Dinge, die du ausprobieren könntest.
- Momentan funktioniert deine find-Funktion wahrscheinlich nur für Slices von Zahlen,
aber das Typsystem von Rust ist flexibel genug, um eine find-Funktion zu schreiben,
die auf allen Slices funktioniert, deren Elemente sich ordnen lassen.
- Außerdem kann diese find-Funktion nicht nur auf Slices arbeiten, sondern gleichzeitig
auch auf einem Vec oder einem Array.
Um die Bonus-Tests auszuführen, entferne das #[ignore]-Flag und führe die Tests mit
dem generic-Feature aus, so:
$ cargo test --features generic
Dann teile bitte deine Gedanken in einem Kommentar zu deiner Lösung mit. Hat dieses
Experiment den Code besser gemacht? Schlechter? Hast du etwas daraus gelernt?
