Dein Fortschritt:
0 / 0 Aufgaben
1
Die Mitgliederliste
AFB I–IIEin Sportverein speichert die Nachnamen seiner Mitglieder alphabetisch sortiert in einer Reihung namen. Die Suche verwendet compareTo: s.compareTo(t) ist negativ, wenn s alphabetisch vor t steht, 0 bei Gleichheit und sonst positiv.
Material 1: Ausschnitt der Reihung (Länge 10)
namenArndt0Becker1Celik2Dietz3Engel4Frank5Gerlach6Hoppe7Iwanow8Jansen9
Material 2: Methode suche
static int suche(String[] namen, String gesucht, int links, int rechts) {
if (links > rechts) {
return -1;
}
int mitte = (links + rechts) / 2;
int v = namen[mitte].compareTo(gesucht);
if (v == 0) {
return mitte;
}
if (v < 0) {
return suche(namen, gesucht, mitte + 1, rechts);
}
return suche(namen, gesucht, links, mitte - 1);
}- Beschreiben Sie die Rolle von
vin der Methode und nennen Sie die Voraussetzung, unter der die Suche korrekt arbeitet. 3 BE - Stellen Sie die Aufrufe von
suche(namen, "Hoppe", 0, 9)undsuche(namen, "Brandt", 0, 9)jeweils mitlinks,rechts,mitteundnamen[mitte]dar. 5 BE - Ändern Sie die Methode so ab, dass sie bei erfolgloser Suche nicht −1, sondern \(-(p + 1)\) liefert, wobei \(p\) die Position ist, an der der Name einsortiert werden müsste. 4 BE
- Schätzen Sie für einen Landesverband mit 80 000 Mitgliedern ab, wie viele Vergleiche eine Suche höchstens braucht und wie viele Rahmen dabei höchstens auf dem Aufrufstapel liegen. 3 BE
Insgesamt 15 BE
Hinweise
Hinweis zu Aufgabe a)
Vergleichen Sie mit der Suche auf Zahlen: Was entspricht dort
a[mitte] < x?Hinweis zu Aufgabe b)
Für „Brandt“: B-r kommt nach B-e, aber vor C.
Hinweis zu Aufgabe c)
Wo stehen
links und rechts, wenn der Bereich leer wird?Hinweis zu Aufgabe d)
Nutzen Sie \(\lfloor \log_2 n \rfloor + 1\) und berücksichtigen Sie den Aufruf mit leerem Bereich.