Geometrische Suche

Die geometrische Suche ist ein Suchalgorithmus, der in einem sortierten Array die Position eines gesuchten Wertes ermittelt bzw. feststellt, dass der Wert nicht im Array enthalten ist. Die geometrische Suche wird vor allem dann eingesetzt, wenn man davon ausgeht, dass sich der gesuchte Wert eher im vorderen Teil des Arrays befindet. Der Name ergibt sich aus der verwendeten geometrischen Folge.

Beschreibung

Die Funktionsweise der geometrischen Suche wird durch folgenden Algorithmus skizziert:

Eingabe: Array a, gesuchtes Element x

Sei n dazu die Länge des Arrays a:

1. Setze i: = 0.
2. Falls n < 2ⁱ, durchsuche den Bereich von 2^{i − 1} + 1 bis n mit binärer Suche.
3. Falls $x\leq a[2^i]$: Durchsuche den Bereich 2^{i − 1} + 1 bis 2ⁱ mit binärer Suche.
4. Falls x > a[2ⁱ]: Setze i: = i + 1 und fahre mit 2. fort.

Der Suchraum wird also verkleinert, indem nacheinander die Positionen $2^0,2^1,2^2,\dots$ betrachtet werden. Auf dem verkleinerten Suchraum wird die gesuchte Position dann mit binärer Suche ermittelt.

Im Worst Case befindet sich das gesuchte Element an der letzten Arrayposition. Im ersten Teil des Algorithmus (Vergleiche mit $2^0,2^1,2^2,\dots$) werden dann log n wesentliche Vergleiche benötigt, genauso wie im zweiten Teil (binäre Suche). Zusammen ergibt sich eine Worst Case-Rechenzeit von $\mathcal{O}(\log n)$.