G
Guest
Gast
Hallo, soll für die Uni eine Aufgabe zu BinarySearch bearbeiten.
Habe folgende Aufgabenstellung:
In der Vorlesung wurde ein imperativer Algorithmus für das binäre Suchen in geordneten Feldern vorgestellt.
a) Zeigen Sie an einem geeigneten Zahlenbeispiel wie dieser Algorithmus funktioniert.
b) Schreiben Sie eine rekursive Methode für dieses Suchverfahren. Wenn der Wert gefunden wurde, soll der Index
des gefundenen Wertes zurückgeben werden, im anderen Fall soll der Rückgabewert -1 sein.
Fügen Sie in diese Methode einen Zähler ein, der alle Vergleiche zählt.
c)Schreiben Sie ein Testprogramm für das binäre Suchen. Wählen Sie als Feldgröße 100, 1 000, 10 000 und 100 000
Werte, geben Sie die Position des gefundenen Wertes sowie die Anzahl der Vergleiche aus.
a und c hab ich fertig. b eigentlich auch. allerdings weiss ich jetzt nicht genau ob ich die Aufgabenstellung voll erfüllt habe. Könnt ihr euch das nur mal kurz anschauen und mir sagen ob es soweit stimmt.
Danke!!!!
Habe folgende Aufgabenstellung:
In der Vorlesung wurde ein imperativer Algorithmus für das binäre Suchen in geordneten Feldern vorgestellt.
a) Zeigen Sie an einem geeigneten Zahlenbeispiel wie dieser Algorithmus funktioniert.
b) Schreiben Sie eine rekursive Methode für dieses Suchverfahren. Wenn der Wert gefunden wurde, soll der Index
des gefundenen Wertes zurückgeben werden, im anderen Fall soll der Rückgabewert -1 sein.
Fügen Sie in diese Methode einen Zähler ein, der alle Vergleiche zählt.
c)Schreiben Sie ein Testprogramm für das binäre Suchen. Wählen Sie als Feldgröße 100, 1 000, 10 000 und 100 000
Werte, geben Sie die Position des gefundenen Wertes sowie die Anzahl der Vergleiche aus.
a und c hab ich fertig. b eigentlich auch. allerdings weiss ich jetzt nicht genau ob ich die Aufgabenstellung voll erfüllt habe. Könnt ihr euch das nur mal kurz anschauen und mir sagen ob es soweit stimmt.
Danke!!!!
Code:
// binäre Suche rekursiv
public static int binSucheR(int[] feld, int wert, int unten, int oben) {
anzApp++;
if (unten > oben)
return -1;
else if (feld[(oben + unten) / 2] == wert)
return (oben + unten) / 2;
else if (feld[(oben + unten) / 2] < wert)
return binSucheR(feld, wert, (oben + unten) / 2 + 1, oben);
else
return binSucheR(feld, wert, unten, (oben + unten) / 2 - 1);
}