Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Felder sortieren Mergesort Indices

2.7 Intervallhalbierung

Eine einfache Suche in einem Feld kann beginnend vom ersten Element der Reihe nach jedes Element vergleichen. Diese lineare Suche vergleicht im ungünstigsten Fall jedes Element, wenn das zu suchende das letzte in dem Feld ist. In einem sortierten Feld kann mit dem Motto "Teile und Herrsche" die Suche beschleunigt werden. Der Algorithmus geht wie folgt:

  1. Nimm das Element in der Mittes des Feldes. Der Index wird immer abgerundet.
    Ist es das gesuchte, ist man fertig.
  2. Ist das gesuchte Element größer als das in der Mitte, betrachte das dahinter liegende Teilfeld, andernfalls das davor liegende.
  3. Führe die Schritte 1 - 2 für das neue Teilfeld durch.

Dazu ein Beipiel mit 10 Einträägen in dem Feld, gesucht wird das Element 3. Der erste Index hat den Wert 0 wie in dem in C formulierten Beispiel.

0 1 2 3 4 5 6 7 8 9

Die Mitte ist 5, da 3 kleiner ist, nehmen wir das davor liegende Teilfeld.

0 1 2 3 4

Die Mitte ist 2, da 3 größer ist, nehmen wir das dahinter liegende Teilfeld.

3 4

Die Mitte ist 4, da 3 kleiner ist, nehmen wir das davor liegende Teilfeld.

3

Wir haben das Element gefunden.

Achtung, die folgenden Beispiele funktionieren nur, wenn das zu suchende Element auch in dem Feld vorhanden ist!

Beispielcode
Home Felder sortieren Mergesort Indices


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum