Such-Algorithmen - Lineare Suche / Binäre Suche

Lineare Suche

Beispiel: ...

Binäre Suche

Im folgenden Beispiel wird in der Datei BEISPIEL.DAT nach einem Wort gesucht, das in der Variable Suchwort$ gespeichert ist. Jede Zeile der Beispieldatei ist genau 100 Byte lang und besteht aus 98 (mehr oder weniger) beliebigen Zeichen und den beiden abschließenden ASCII-Zeichen CR und LF für den Zeilenumbruch.

  Datei = FileOpen geosPath$ + "\\BEISPIEL.DAT"
  IF fileError <> 0 THEN Abbruch
  Minzeile = 0
  Maxzeile = FileSize(Datei) -100
    REPEAT
      Istzeile = Int((Minzeile / 100 + Maxzeile / 100) /2)
      Istzeile = Istzeile * 100
      FileSetPos Datei, Istzeile
      Fund$ = FileRead(Datei, Laenge)
      Fund$ = Convert$(Fund$, downcase_CHARS)
      IF CompStr(Suchwort$, Fund$) = 0 THEN Gefunden : BREAK
      IF CompStr(Suchwort$, Fund$) = -1 THEN Maxzeile = Istzeile - 100
      IF CompStr(Suchwort$, Fund$) = +1 THEN Minzeile = Istzeile + 100
      IF Maxzeile < Minzeile THEN NichtGefunden : BREAK
    UNTIL flag = 1
  FileClose Datei
  Datei = NullFile()

Zuerst wird im GEOS-Stammverzeichnis die Datei BEISPIEL.DAT geöffnet. Tritt dabei ein Fehler auf, soll das Unterprogramm Abbruch angesprungen werden.

Dann die Dateigröße herausfinden und in zwei Variablen speichern. Der Anfangswert "0" vor dem ersten Zeichen ist klar und muss nicht berechnet werden. Von der errechneten Größe des Dateiendes wird 100 abgezogen, da jede Zeile 100 Bytes lang ist und die Suche immer den Zeilenanfang vergleicht - und der Zeilenanfang der letzten Zeile ist 100 Bytes vor dem Ende der Datei zu finden.

Nun die eigentliche Suche. Der "Trick" der Binären Suche besteht im Ausschließen der Bereiche, die aufgrund der alphabetischen Sortierung für das Suchwort nicht in Frage kommen. Dazu springt die Suche zu einer Zeile in der Mitte der Datei und prüft, ob das Suchwort alphabetisch vor oder hinter dieser Zeile liegt. Mit diesem ersten Vergleich scheidet also schon einmal eine Hälfte der Datei aus. Dann wird der verbliebene Rest geteilt und wieder verglichen und so weiter.

Weil die Suche (mit dem Befehl FileSetPos) immer am Anfang einer Zeile "landen" muss, um das Suchwort mit der Zeile vergleichen zu können, ist es wichtig, dass jede Zeile genau gleich lang ist. Weiterhin muss natürlich die Länge der Zeilen bekannt sein (im Beispiel 100 Zeichen). In einer Beispieldatei von 10.000 Bytes Größe und jeweils 100 Bytes langen Zeilen ergibt eine Teilung durch zwei also z.B. 5000, dann 2500, dann 1250, usw. Weil bei 1250 der Dateizeiger aber mitten in der Zeile landen würde, muss der Wert vorher durch 100 geteilt (ergibt 12,5) und der Rest hinter dem Komma mit den Befehl Int gekürzt werden. Das Ergebnis wieder mal 100 genommen und schon landet der Dateizeiger am Anfang der Zeile 1200.

Der Befehl CompStr() vergleicht die zwei Zeichenketten Suchwort$ und Fund$ miteinander und liefert je nach Ergebnis einen anderen Wert zurück. Der Wert 0 (Null) signalisiert, dass die Suche erfolgreich war und das Wort gefunden wurde. Der Wert -1 signalisiert einen zu weiten Sprung, also dass das Suchwort weiter vorne in der Dateiliste liegt. Der Wert +1 signalisiert einen zu kurzen Sprung, das Suchwort liegt also weiter hinten in der Dateiliste. Da die aktuelle Zeile für die weitere Suche bereits als falsch ausscheidet, wird der Dateizeiger um 100 Bytes nach oben oder unten versetzt und dort der neue Startpunkt (bzw. Endpunkt) für einen weiteren Suchlauf festgelegt.

Wird das Suchwort nicht in der Datei gefunden, springt das Programm zum Unterprogramm NichtGefunden.

Jetzt noch die Datei schließen und das war's schon mit der Binären Suche.

Weiterführende Links

PS

• Die hier gezeigte Lösung funktioniert bei mir. Es ist aber durchaus möglich, dass es andere, clevere Möglichkeiten gibt, die Binäre Suche in einem R-Basic Programm umzusetzen.

• Sie experimentieren auf eigenens Risiko. Sollte Ihr Rechner explodieren, streite ich jede Beteiligung ab ;-)