Quadratische Binärsuche

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

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}}}$.

Komplexität

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]

Einzelnachweise

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