Quadratische Binärsuche

Quadratische Binärsuche i​st ein Suchalgorithmus ähnlich d​er Binärsuche o​der Interpolationssuche. Es versucht d​urch Reduzierung d​es Intervalls i​n jedem Rekursionsschritt d​ie Nachteile d​er Interpolationssuche z​u 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 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 .

Komplexität

Wie bei der Interpolationssuche ergibt sich im mittleren Fall eine Laufzeit von , im schlechtesten Fall jedoch nur eine Laufzeit von .[1]

Einzelnachweise
  1. Suchen in linearen Feldern (PDF; 142 kB), Technische Universität Graz
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.