Quadratische Binärsuche
# 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 ${\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

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

