is-Logo

Suchen und Sortieren
- Binäres Suchen -

S. Spolwig

[Home | Algorithmen]

Wer einen Namen im Telefonbuch sucht, macht sich die alphabetische Reihenfolge zu nutze. Er schlägt das Buch etwa in der Mitte auf. Hier findet man entweder sofort den Namen oder er liegt in der vorderen oder hinteren Hälfte. In der entsprechenden Hälfte tut man das gleiche wieder. Nach  endlich vielen (oder relativ wenigen) Versuchen hat man den Namen gefunden oder er ist nicht eingetragen.

Damit ist ein allgemeines Lösungsprinzip beschrieben: "Divide and conquer".

            Ein Problem wird solange zerlegt, bis die Lösung offensichtlich ist.
     Die Problemstellung bleibt für jedes Teilproblem die gleiche.

 

Binäres Suchen (Suchen durch Halbieren)

Die Methode besteht darin, das mittlere Element zu bestimmen und mit dem Suchschlüssel (key) zu vergleichen. Beim Treffer ist die Suche beendet, sonst wird je nachdem, ob key größer oder kleiner als das Vergleichselement ist, die dieselbe Suchmethode auf das linke oder rechte Teilfeld angewendet.

Ist das Element nicht enthalten, wird beendet, wenn nichts mehr zu teilen ist.

Diese Strategie führt zu einem rekursiven Verfahren, wobei die Suchmethode sich selbst für die linke und rechte Seite aufruft.

 

     Key = U

[1] [2] [3] [4] [5] [6] [7] [8] [9]
A C F G K L R U X
A C F G K L R U X
A C F G K L R U X

Aufgabe:  Bearbeiten Sie das folgende Übungsblatt!



©    05. Oktober 2008   Siegfried Spolwig

page_top