Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

38.4 Interpolierende Suche

38.4 Interpolierende Suche

Dieses Verfahren versucht nun folgende Problematik zu umgehen. Angenommen Sie suchen in New York, eine Person mit dem Nachnamen "Zwicker" im Telefonbuch. Nach dem Intervallhalbierungsverfahren, müssten Sie das Buch in der Mitte aufschlagen, dann vom Rest noch einmal die Hälfte und so weiter und so weiter. Somit brauchen Sie trotzdem relativ lange, um ein Element am Ende einer Liste zu finden. Wenn man sich aber selber mal beobachtet, dann sucht man in einem Telefonbuch anders. Man schlägt gleich den Teil auf, in welchem Namen mit Z stehen und dann sucht man nach "Zw", was erheblich schneller geht. Genau dies wird durch dieses Verfahren annähernd realisiert. Bei der Interpolation wird quasi eine bessere "Mitte" geschätzt, so dass man die Liste nicht teilt, sondern drittelt, viertelt oder sogar in einen noch kleineren Bereich teilt.

Dummerweise funktioniert dieses Verfahren aber nicht bei Texten, sondern nur bei Zahlen und dann auch nur, wenn die Zahlen verhältnismäßig gleich verteilt sind. Der Grund ist folgender. Es wird vom ersten und letzten Element der Betrag gebildet und die Länge des Bereiches ermittelt. Anschließend wird eine Art Prozentwert für das zu suchende Element gebildet, welcher der tatsächlichen Position entspricht oder ihr sehr nahe kommt. Stimmt die Position noch nicht, wird der Bereich verkleinert und der Spaß beginnt von vorne. Folgende Grafik wird dies an einem konkreten Beispiel demonstrieren.

Veranschaulichung der interpolierenden Suche

In diesem Beispiel wird das zu suchende Element, bereits im ersten Durchlauf gefunden. Wäre dies nicht der Fall, würde geprüft werden, ob die neue Mitte kleiner oder größer ist, als das zu suchende Element. In dem Fall das es größer ist, wird die linke Grenze auf Mittelwert plus eins gesetzt und im Fall das es kleiner ist, wird die rechte Grenze auf Mittelwert minus eins gesetzt. Entspricht die linke und die rechte Grenze nicht dem gesuchten Wert, wird wieder die Formel angewandt.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012