Quadratische Binärsuche

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

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.

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 ${\displaystyle {\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 ${\displaystyle {\sqrt {n}}}$.

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

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