Lektion 66:

Binäres Suchen

Wie Sie gesehen haben, ist es möglich mit nur sieben Ja/Nein-Abfragen eine Zahl zwischen 0 und 99 zu finden. Mit nur 10 Abfragen kann man den Bereich bis 1000 abdecken. Mit nur 20 Abfragen bis zu 1000000. Allgemein kann man mit n Abfragen eine Zahl aus 2^n Zahlen finden. Würde man die Zahlen einfach nur der Reihe nach ausprobieren, dann bräuchte man für einen Bereich von n Zahlen n/2 Versuche.

 Das Verfahren dafür heißt binäres Suchen. Mit diesem Verfahren lassen sich auch in einem Array bestimmte Werte suchen. Voraussetzung ist allerdings, daß die Daten sortiert vorliegen. Die schnellen Zugriffszeiten auf sortierte Listen sind der Grund dafür, daß das Sortieren auf Computern einen so großen Stellenwert einnimmt.

Um die Klasse Set mit dem neuen Suchverfahren auszustatten, müssen zwei kleine Veränderungen vorgenommen werden:

  • Die findIndex-Methode muß neu programmiert werden, damit sie das neue Verfahren verwendet, und
  • die insert-Methode muß neu programmiert werden, damit sie die Sortierung aufrechterhält.

Übung (sehr schwierig)

Programmieren Sie diese beiden Methoden. Die findIndex-Methode ist wirklich ein wenig tückisch. Wenn Sie Probleme damit haben, dann verfahren Sie wie bei den Sortierverfahren und legen sich ein paar Münzen auf den Tisch, die das Array darstellen und testen Sie daran ihr Verfahren. Für die insert-Methode ist es günstig, in der Klasse Vector eine moveUp-Methode einzuführen.

Einsendungen:

Lösungsvorschlag für findIndex


Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00