Quadratische Binärsuche

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

Quadratische Binärsuche ist ein Suchalgorithmus ähnlich der Binärsuche oder Interpolationssuche. Es versucht durch Reduzierung des Intervalls in jedem Rekursionsschritt die Nachteile der Interpolationssuche zu vermeiden.

Idee[Bearbeiten]

Nach dem Muster der Interpolationssuche wird zunächst in jedem rekursiven Schritt die vermutete Position k interpoliert. Anschließend wird – um die Nachteile der Interpolationssuche zu vermeiden – das Intervall der Länge \sqrt{n} gesucht in dem sich der gesuchte Wert befindet. Auf dieses Intervall wird der nächste rekursive Aufruf der Suche angewendet.

Auf diese Weise verkleinert sich der Suchraum bei gegebener Liste der Länge n bei jedem rekursiven Schritt auf eine Liste der Länge \sqrt n.

Komplexität[Bearbeiten]

Wie bei der Interpolationssuche ergibt sich im mittleren Fall eine Laufzeit von \mathcal{O}(\log(\log(n))), im schlechtesten Fall jedoch nur eine Laufzeit von \mathcal{O}(\sqrt{n}).[1]

Einzelnachweise[Bearbeiten]

  1. Suchen in linearen Feldern (PDF; 152 kB), Technische Universität Graz