Binäre Listensuche

Die Binäre Suche funktioniert nur mit sortierten Listen. Die Idee: Angenommen Sie haben eine Liste aus Werten, dann starteten Sie die Suche in der Mitte der Liste und teilen die zwei entstandenen Bereiche in einen mit größeren Werten und kleineren Werte auf. Ist nun der größte Wert des "niederwertigen" Bereichs größer als die gesuchte Zahl, wissen Sie, dass die gesuchte Zahl in diesem Bereich liegen muss. Nun teilen Sie den niederwertigen Bereich wiederum in einen niederwertigen und in einen höherwertigen Bereich ein und beginnen von neuem. Diese Technik kennen Sie bereits als Teilen und Herrschen oder Divide and Conquer.

Das Prinzip wird beispielsweise auch bei binären Suchbäumen angewendet. Dazu später mehr.

Der Algorithmus in Worten:

1. Finde die Mitte der Liste.
2. Ist die Mitte das Ziel, dann brich ab!
3. Hat das Ziel eine grössere Zahl, so setze die Mitte als den Anfang.
4. Hat das Ziel eine kleinere Zahl, so setze die Mitte als das Ende.
5. wiederhole bei 1.

Überlegen Sie sich, wie der Algorithmus arbeitet. Skizzieren Sie sich dazu einen Zahlenstrahl, und suchen eine bestimmte Zahl daraus.

So könnte der Code in MatLab aussehen:

Vergleichen Sie die Suchdauer mit der Listensuche. Welche Suche ist in diesem Fall schneller (braucht weniger Schritte für die Suche). Welche Suche ist im Durchschnitt schneller?

In diesem Fall arbeiten wir mit einem Array von Buchstaben (also ein String). Wie müssten Sie den Algorithmus anpassen um einen struct -array zu durchsuchen?