Binäre Suche in geordnetem Array (Algorithmus 3.2)

So geht’s: Beim Öffnen ist derselbe Testclient geladen wie bei der sequenziellen Suche: Die Buchstaben von SEARCHEXAMPLE kommen mit put in die Tabelle, der Wert ist die Position im Wort. „Abspielen“ oder „Schritt“ zeigt jeden Vergleich in rank: Die Marken lo, hi und mid stehen über den beiden Arrays, keys[mid] ist blau, alles außerhalb von lo..hi wird blass. Ist der Schlüssel neu, rücken die größeren Einträge einzeln eine Stelle nach rechts (grün), dann kommt der neue orange an seinen Platz. Oben kann man eigene Schlüssel eintragen und suchen und die geordneten Operationen ausprobieren: min, max, select(k), ceiling, floor und keys für einen Bereich. Das Protokoll zeigt jedes rank wie Abbildung 3.6 und darunter alle Operationen mit Vergleichen und verschobenen Einträgen. „↺ Neu starten“ lädt den Testclient neu.

Erklärung

Binäre Suche in geordnetem Array (Algorithmus 3.2), Klasse BinarySearchST. Gleiche Aufgabe wie [22], aber die Schlüssel liegen sortiert in einem Array. Dadurch geht Suchen viel schneller.

Aufbau (Listing 3.5):

• Zwei parallele Arrays: keys[] (sortiert) und vals[]. Zu keys[i] gehört vals[i].
• Key extends Comparable<Key>: Schlüssel müssen vergleichbar sein, equals() reicht nicht mehr.
• Größenanpassung wie bei Algorithmus 1.1 [14], hier weggelassen.

Das Herzstück: rank(key) (Listing 3.7)

• Liefert die Anzahl der Schlüssel, die kleiner als key sind.
• Klassische binäre Suche: Mitte anschauen. Kleiner → links weiter (hi = mid-1), größer → rechts weiter (lo = mid+1), gleich → mid zurück.
• Endet die Schleife ohne Treffer, ist lo genau die Stelle, an die der Schlüssel gehören würde.

Abbildung 3.6 (keys = A C E H L M P R S X):

• Suche nach P: mid 4 (L) zu klein → mid 7 (R) zu groß → mid 5 (M) zu klein → mid 6 (P) Treffer, Rückgabe 6.
• Suche nach Q: gleicher Weg bis mid 6 (P), zu klein, lo wird 7, lo > hi, Rückgabe 7. Genau 7 Schlüssel sind kleiner als Q, und an Index 7 müsste Q eingefügt werden.

get und put:

• get: rank aufrufen, steht an dieser Stelle der Schlüssel, Wert zurück, sonst null.
• put: rank aufrufen. Schlüssel vorhanden → Wert überschreiben. Sonst alle größeren Einträge eine Stelle nach rechts schieben und den neuen an Position i einsetzen. Das Verschieben ist der teure Teil.

Geordnete Operationen (Listing 3.8), praktisch geschenkt, weil alles sortiert ist:

• min(): keys[0], max(): keys[N-1], select(k): keys[k].
• ceiling(key): kleinster Schlüssel ≥ key, einfach keys[rank(key)]. (Kleiner Haken im Buchcode: Ist key größer als alle Schlüssel, ist rank = N und der Zugriff geht über das Array hinaus. Da gehört eigentlich eine Prüfung hin.)
• keys(lo, hi): alle Schlüssel im Bereich, gesammelt in einer Queue aus [16].
• floor() und delete() sind Übungen (3.1.17 und 3.1.16).

Kosten:

• Suche: höchstens lg N + 1 Vergleiche, egal ob erfolgreich oder nicht.
• Einfügen: im schlimmsten Fall ~2N Arrayzugriffe wegen des Verschiebens.
• N Einfügungen in leere Tabelle: quadratisch.

Vergleich mit [22]:

Suchen ist gelöst, Einfügen nicht. Genau das löst als Nächstes der binäre Suchbaum (Algorithmus 3.3): logarithmisches Suchen und Einfügen.