Tutorium Algorithmen und Datenstrukturen 2

Übungsblatt 5: Fortgeschrittene Suchverfahren

Aufgabe 5-1*

Implementieren Sie einen binären Suchalgorithmus für Arrays vom Typ int[].

Tipp. Verwenden Sie folgende Methodensignatur:
int find (int[] array, int key, int leftIndex, int rightIndex)

Zur Erinnerung: Das Prinzip der binären Suche besteht darin, die Mitte des (sortierten) Suchraums zu betrachten und anschließend den Suchraum für die weitere Suche auf eine der beiden Hälften einzuschränken. Die Mitte des Suchraums ergibt sich aus folgender Formel:
m = (r + l) / 2

Aufgabe 5-2

Schätzen Sie grob das Laufzeitverhalten des Algorithmus zur binären Suche auf einer linearen Liste ab.

Aufgabe 5-3*

Das Prinzip der binären Suche besteht darin, die Mitte des Suchraums zu betrachten und anschließend den Suchraum für die weitere Suche auf eine der beiden Hälften einzuschränken. Die Mitte des Suchraums ergibt sich aus folgender Formel:
m = (r + l) / 2 = l + (r − l) · ½

Anstatt ungezielt die Mitte zu nehmen, kann man auch schätzen, an welcher Position sich der gesuchte Schlüssel wahrscheinlich befindet. Anstelle der Mitte wird dann diese geschätzte Position betrachtet. Die folgende Formel ersetzt den Faktor ½ durch eine lineare Interpolation.
m = l + (r − l) · (k − A_l) / (A_r − A_l)

Implementieren Sie das Verfahren der Interpolationssuche in einer Methode analog zu Aufgabe 5-1.

Aufgabe 5-4

Die folgenden Teilaufgaben beziehen sich allgemein auf die in der Vorlesung behandelten Verfahren zum Suchen und Finden von Daten; es können beliebige Bedingungen an die Speicherung der Daten gestellt werden (etwa, dass sie sortiert sein müssen). Begründen Sie jeweils Ihre Antwort, z. B. durch Nennung des Namens eines geeigneten Verfahrens.

1. Gibt es ein Suchverfahren, das regelmäßig (also im average case) mit konstantem Zeitaufwand O(1) zum Ergebnis führt?
2. Gibt es ein Suchverfahren, das im average case einen höheren als linearen Zeitaufwand O(n) hat?
3. Gibt es ein Suchverfahren, das im worst case einen geringeren als linearen Zeitaufwand O(n) hat?
4. Welche(s) Verfahren sollten Sie selbst bevorzugt einsetzen? Weshalb?

Zusatzaufgabe 5-5*

Beim Schritt von der binären Suche in Aufgabe 5-1 zur Interpolationssuche in 5-3 wurde die Effizienz der Suche verbessert, indem die Anzahl der nötigen Vergleiche deutlich minimiert wurde bei gleichzeitiger Inkaufnahme eines leicht erhöhten Rechenaufwands.

Die Fibonacci-Suche verfolgt einen anderen Ansatz zur (theoretischen) Verbesserung der Effizienz der binären Suche: Sie benötigt in etwa gleich viele Vergleiche, hat dabei aber (theoretisch) einen noch geringeren Rechenaufwand als die binäre Suche.

Implementieren Sie das Verfahren der Fibonacci-Suche in einer Methode analog zu Aufgabe 5-1.

$Id: HEADER.html,v 1.1 2008/05/21 01:39:58 aj3 Exp $

 Name                                   Last modified      Size  Description
 Parent Directory                                            -   
 Loesung54.html                         2023-10-11 10:00  7.1K  Lösungsvorschlag zu Aufgabe 5-4 – Tutorium Algorithmen und Datenstrukturen – SS 2008
 README.html                            2023-10-11 10:00  961   
 RandomisedArrayFactory.java            2023-10-11 10:00  5.7K  
 Loesung55.java                         2023-10-11 10:00  7.8K  
 Loesung53.java                         2023-10-11 10:00  2.9K  
 Loesung51.java                         2023-10-11 10:00  2.9K  
 KeyNotFoundException.java              2023-10-11 10:00  346   
 HEADER.html                            2023-10-11 10:00  3.6K