Suchen und Halbieren

Schnelle Halbier-Suche

Die schnelle Halbier-Suche kann ein Computer nur dann anwenden, wenn eine Liste sortiert ist.

Wie funktioniert die Halbiersuche?

1. Um deine eingetippte Zahl in der Liste zu finden, schaut sich nibble im ersten Schritt die Zahl an der Position 8 in der Mitte der Liste an. Indem nibble die Mitte sucht, wird die Liste halbiert, nibble hat nun eine obere und eine untere Hälfte.
2. Nun weiss nibble, dass die Liste aufsteigend sortiert ist. nibbel braucht also nur noch die gesuchte Zahl mit der Zahl an der Position 8 zu vergleichen. Wir nehmen jetzt an, dass die gesuchte Zahl kleiner ist, dann liegt sie sicher nicht in der oberen Hälfte der Liste. Deshalb beachtet nibble von jetzt an nur noch die untere Hälfte der Liste. Irgendwo in dieser unteren Hälfte muss die gesuchte Zahl stecken.
3. Nun halbiert nibble die restliche Liste noch einmal. Sucht die neue Mitte und vergleicht die Zahl an dieser Position wieder mit der gesuchten Zahl. Wenn die gesuchte Zahl grösser ist, so wird in der oberen Hälfte weitergesucht.
4. Die wird so lange fortgesetzt, bis nur noch eine Zahl in der Liste übrig ist. Entweder ist diese Zahl nun die gesuchte Zahl oder die gesuchte Zahl ist nicht in der Liste vorhanden gewesen.
5. nibble benötigt bei dieser Anzahl Zahlen in der Liste immer nur vier Vergleiche. Darum kann nibble bei der Wette gar nie verlieren.

Und weiter geht's mit sortieren ...

< Zurück | Weiter >
<  Zur Übersicht  >