Binäre Suche

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.

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.

Verhalten

Deine Lösung sollte sich bei den Testfällen genauso verhalten wie Julias eingebaute searchsorted-Funktionen. Das heißt: Statt den Index des ersten passenden Elements zurückzugeben, das du in der Liste findest, gibst du einen Bereich zurück, dessen untere Grenze der Index des ersten passenden Elements in der Liste ist und dessen obere Grenze der Index des letzten passenden Elements in der Liste ist. Zur Vereinfachung deiner Lösung darfst du allerdings annehmen, dass das gesuchte Element nicht mehrfach vorkommt, außer im Bonustestset zu mehreren Treffern.

Wenn das gesuchte Element nicht in der Liste vorkommt, musst du einen leeren Bereich zurückgeben, dessen untere Grenze der Index ist, an dem das Element in die sortierte Liste eingefügt werden könnte. Ein leerer Bereich ist jeder Bereich, bei dem die obere Grenze kleiner als die untere Grenze ist.

Lies bitte die Dokumentation und die Beispiele zur Funktion searchsorted, wenn du mehr wissen möchtest:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

Bonusaufgaben

• Erweitere deine Lösung so, dass sie die Schlüsselwortargumente by, lt und rev unterstützt: by gibt eine Transformation an, die auf alle Elemente der Liste angewendet wird, lt gibt einen Vergleich an und rev gibt an, ob die Liste umgekehrt sortiert ist. Wenn diese Parameter verwendet werden, musst du davon ausgehen, dass die Liste bereits mit ihnen sortiert wurde. Weitere Einzelheiten findest du in der Dokumentation zu sort.
• Unterstütze Listen, in denen das gesuchte Element mehrfach vorkommt (finde den ersten und letzten Index, an dem das gesuchte Element als gleich verglichen wird).

---

Quelle

Wikipedia