A.1.4 Binäre Suche

(aus [v.Helden] übernommen)

Das Suchverfahren ,,Binäres Suchen`` arbeitet nach folgendem Algorithmus:

Algorithmus: Binäre Suche im Array a[min .....max] // min = 0, max = n

  1. wähle ein mittleres Element des Arrays a[mid]
  2. if (a[mid].key == gesuchterKey)
    Suche erfolgreich
    else
    if (a[mid].key < gesuchterKey)
    betrachte die rechte Hälfte des Arrays mid .. max
    else
    betrachte die linke Hälfte des Arrays 0 .. mid
  3. if (betrachtetes Array == leer)
    Suche erfolglos
    else
    beginne bei Schritt 1

Implementieren Sie den Algorithmus so, daß in einem sortierten Feld von Integer-Zahlen gesucht werden kann. Geben Sie jedesmal, wenn Sie ein Teilfeld durchsuchen, die Indizes der Grenzen und des mittleren Elements aus. Geben Sie am Ende den Index des gefundenen Elements bzw. eine Meldung für die erfolglose Suche aus.

Testen Sie Ihren Algorithmus zunächst mit einfachen Feldern, die Sie direkt im Programmcode initialisieren.

Erweitern Sie ihr Programm so, daß die zu durchsuchende Zahlenfolge aus einer Datei eingelesen werden kann. Hierzu sollen Sie folgende Ein-/Ausgabe realisieren:

Geben Sie zum Schluß den Algorithmus richtig an (im Gegensatz zum oben gegebenen).

www.wachtler.de