Implementieren Sie einen sequentiellen Suchalgorithmus in einer Methode. Die Methode soll als Parameter einen Array vom Typ int[] und einen Wert vom Typ int übergeben bekommen; dieser Wert ist in diesem Array zu suchen. Zurückgegeben werden soll der Array-Index der Fundstelle.
Implementieren Sie einen binären Suchalgorithmus in einer weiteren Methode analog zu Aufgabe 7-1.
(Vorsicht! Im Skript werden auch binäre Suchbäume behandelt. Bei dieser Aufgabe soll aber nicht in irgendwelchen Bäumen gesucht werden, sondern in einem Array vom Typ int[], genau wie bei Aufgabe 7-1. Dazu muss der Algorithmus aus dem Kapitel 7.2.2 implementiert werden. In dem im Skript befindlichen Algorithmus ist jedoch ein Fehler: In der ersten Zeile ist „Falls n > 1“ nicht richtig; es müsste eigentlich „Falls n ≥ 1“ heißen und unter „Start“ eingerückt stehen.)
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
Schätzen Sie grob das Laufzeitverhalten des Algorithmus zur binären Suche auf einer linearen Liste ab.
Implementieren Sie einen weiteren sequentiellen Suchalgorithmus in einer Methode. Diese Methode soll als Parameter eine lineare Liste vom Typ LinearList (vgl. Aufgabe 6-1) und einen Wert vom Typ int übergeben bekommen; dieser Wert ist in dieser Liste zu suchen. Zurückgegeben werden soll die Fundstelle selbst (Rückgabetyp LinearList).
$Id: HEADER.html,v 1.7 2007/12/20 17:28:01 arne Exp $
Name Last modified Size Description
Parent Directory -
HEADER.html 2023-10-11 10:00 2.3K
KeyNotFoundException.java 2023-10-11 10:00 356
LinearList.java 2023-10-11 10:00 349