Binäre Suche in sortierter Liste

Einleitung

Hin und wieder wäre es praktisch, man könnte eine längere Liste schneller als nur linear (oben beginnen, unten aufhören) durchsuchen. Eigentlich bieten sich hierfür eine sortierte Strings-Collection (bis 65k Einträge) oder sortierte Arrays (bis 16k Einträge) in Verbindung mit binärer Suche an. Doch soll die Liste zur Laufzeit verändert werden können, so verhindert dies die Collection schon dadurch, dass sie keine Einträge einfügen, sondern nur anhängen lässt. Damit ist nicht mal mit viel gutem Willen und Aufwand eine sortierte Liste sinnvoll zu unterhalten. Denn aufwendig ist es auch, dies mit einem Array selber zu implementieren.

Liegen die Werte bereits sortiert vor und werden zur Laufzeit nicht verändert, so kann der folgende Algorithmus ohne weiteres an Strings-Collection oder Arrays angepasst werden!

In binsrch.sdw befinden sich Beispiele und der gesamte Programm-Code.

ListBox als sortierte Liste

Eine Workaround für dieses Problem, das allerdings «nur» 4096 Einträge ermöglicht (genügt aber vielfach), ist die Verwendung einer sortierten ListBox. Gehört bereits ein Dialog mit zum Programm, so empfiehlt es sich, die ListBox auf einer Seite anzulegen, die sonst nicht benötigt wird (siehe «Vielseitige Dialoge mit Step»). Ansonsten legt man einen Dialog an, lädt ihn zur Laufzeit, aber zeigt ihn nicht an. Auf die darin enthaltenen Kontrollfelder kann dennoch zugegriffen werden:

...
SortDialog.Load()
' verarbeite die sortierte Liste
SortDialog.SortedList.AddItem("Meier")
...
' suche einen Eintrag
Index% = BinarySearch%(SortDialog.SortedList, "Herger")
' entferne Dialog aus dem Speicher
SortDialog.Unoad()
...

Voraussetzung hierfür ist, dass der SortedList die Eigenschaft «Sorted» gegeben wurde. In diesem Fall übernimmt das SO die Sortierung. Es kommen damit viel effizientere Routinen zum Einsatz, als diese in StarBasic zu implementieren wären.

Binäre Suche

Die binäre Suche gehört wohl ins Programm jedes Programmierkurses. Es ist einer jener grundlegenden Algorithmen, die auch noch zu verstehen sind...

Da wir uns auf die Suche in sortierten Listen beschränken, ist es nicht nötig, die ganze Liste zu durchwühlen. Nehmen wir im folgenden Beispiel einer aufsteigend sortierten Namensliste den Messner, so sind alle davor aufgeführten Werte kleiner, alle danach grösser als dieser.

...
Meissner
Merz
Messner
Metzger
Meyer
...

Wird also zuerst der gesuchte Wert mit demjenigen in der Mitte einer Liste verglichen, so kann der weiter zu durchsuchende Bereich bereits halbiert werden: ist der gesuchte Wert grösser, so kann die erste Hälfte weggelassen werden, sonst die zweite. Verfährt man mit der übrigbleibenden Hälfte wiederum so, so verbleibt noch ein Viertel. Der in jedem Schritt verglichene Wert ist im folgenden Beispiel hervorgehoben dargestellt:

Dies führt, wenn mich meine mathematischen Kenntnisse nicht gänzlich verlassen haben, dazu, dass die binäre Suche im schlimmsten Fall ungefähr folgendes Verhalten aufzeigt:

Mathematisch liesse sich diese Funktion mit (Log₂ n) + 1 beschreiben, wobei n die Anzahl Werte ist ;-).

Der folgende Algorithmus und ein Beispielprogramm sind in binsrch.sdw gespeichert.

Function BinarySearch%(SortedList as Object, ByVal SearchValue$)
   Dim first%    ' Zeiger auf ersten zu vergleichenden Eintrag
   Dim last%     ' Zeiger auf letzten zu vergleichenden Eintrag
   Dim current%  ' Zeiger auf aktuellen Eintrag

   first% = 0
   last% = SortedList.ListCount - 1

   Do While last% >= first%
      ' "mittleren" Wert des aktuellen Bereiches bestimmen
      current% = Fix((first% + last%) / 2)

      ' aktuellen mit gesuchtem Wert vergleichen
      Select Case StrComp(SearchValue$, SortedList.List(current%))

         ' aktueller Wert zu gross: untere Grenze neu festlegen
         Case -1
            last% = current% - 1

         ' aktueller und gesuchter Wert stimmen überein
         Case 0
            Exit Do

        ' aktueller Wert zu klein: obere Grenze neu festlegen
         Case 1
            first% = current% + 1
      End Select
   Loop

   If last% < first% Then
      ' nix gefunden
      BinarySearch% = -1
   Else
      ' Index des gefundenen Wertes zurückgeben
      BinarySearch% = current%
   End If
End Function

Wer sich intensiver mit Algorithmen und Datenstrukturen auseinandersetzen will, dem kann ich die Lektüre des Buches «Algorithmen» von Robert Sedgewick wärmstens empfehlen! Das gibt's zwar «nur» für C und Pascal, aber mit etwas gutem Willen lassen sich die Routinen problemlos nach Basic (oder Java oder ...) übernehmen.

Letzte Änderung: 03.04.98
Copyright ©1998 by Michael Herger