Moin,

kann mir mal jemand erklären, was der Trick bei der zweiseitigen sequentiellen Suche und bei der Fibonacci Suche ist? Irgendwie stehe ich da total auf dem Schlauch.
Bei der zweiseitigen sequentiellen Suche steht, dass nur ein Intervall weiter untersucht werden muss. Aber warum?

Bei der Fibonacci Suche verstehe ich nur, dass man das Intervall anhand der Fibonacci Zahlen aufteilt. Aber wie geht es dann weiter.

Danke für eure Hilfe.

taka

Ich hab zwar DOS nicht gehört und bin über die Fibonacci-Suche
nur zufällig beim P2/P3 Lernen gestolpert. Aber vielleicht
hilft's dir ja trotzdem.

Bei der Fibonacci Suche verstehe ich nur, dass man das Intervall anhand der Fibonacci Zahlen aufteilt. Aber wie geht es dann weiter.

Quasi Rekursiv. Das läuft analog zum binären Suchen: Das
Intervall wird immer weiter eingeteilt, bis man das gesuchte
Element gefunden hat. Das "quasi" deshalb, weil man es
auch effizienter iterativ implementieren kann:

Wenn man einen Bereich der Länge [img]http://mokrates.de/cgi-bin/texstring?F_n-1[/img] durchsucht,
wird der zerlegt in
[img]http://mokrates.de/cgi-bin/texstring?F_n-1%3D(F_%7Bn-1%7D-1)%2B1%2B(F_%7Bn-2%7D-1)[/img]
(die +1 ist das zuerst geprüfte Element, das beim nächsten
Suchschritt ja nicht mehr geprüft werden muss). Wenn das
gesuchte Element nun im oberen Bereich zu suchen ist, muss
man als nächstes das Intervall der Länge [img]http://mokrates.de/cgi-bin/texstring?F_%7Bn-1%7D-1[/img]
zerlegen; oder eben [img]http://mokrates.de/cgi-bin/texstring?F_%7Bn-2%7D-1[/img], wenn man im unteren
Bereich weitersuchen muss. Man nimmt also eine der Zelegungen

[img]http://mokrates.de/cgi-bin/texstring?F_%7Bn-1%7D-1%3D(F_%7Bn-3%7D-1)%2B1%2B(F_%7Bn-2%7D-1)[/img]
[img]http://mokrates.de/cgi-bin/texstring?F_%7Bn-2%7D-1%3D(F_%7Bn-4%7D-1)%2B1%2B(F_%7Bn-3%7D-1)[/img]

vor. Da aber in jedem Fall eines der neuen Teilintervalle die
Länge [img]http://mokrates.de/cgi-bin/texstring?F_%7Bn-3%7D-1[/img] hat, muss man nur [img]http://mokrates.de/cgi-bin/texstring?F_%7Bn-3%7D[/img] zum Index des
gerade geprüften Elements addieren bzw. davon abziehen, um die
Position des nächsten zu prüfenden zu erhalten. Dabei merkt man
sich immer zwei aufeinanderfolgende Fibonacci-Zahlen, denn dann
kann man alle weiteren durch Addieren oder Subtrahieren berechnen.

Die Vorteile bei der Fibonacci-Suche sind wohl, dass man das Ursprungsintervall optimal aufteilt, also so, dass man in möglichst wenig Schritten eine bestimmte Genauigkeit erreicht. Außerdem hat man nur Additionen/Subtraktionen und keine Multiplikationen/Divisionen, was von der Rechenzeit her günstig sein könnte (?).