Die Aufgabe
Übung 12.2-3
Erweitern Sie die Klasse Zahlenum ein Sortierverfahren (siehe Folge 8) sowie um eine Methode
public int suchzeitBinaer(int suchzahl)
welche den sortierten Array nach der oben beschriebenen Methode des binären Suchens durchsucht und die Zahl der Vergleiche als Wert zurückliefert.
Systematisches Vorgehen
Der "Schlüssel zum Erfolg" liegt in dem Pseudo-Quelltext, den Sie bereits von der Hauptseite her kennen:
while links <= rechts do mitte := (links + rechts)/2 if A[mitte] = Schluessel then return mitte if A[mitte] > Schluessel then rechts := mitte-1 if A[mitte] < Schluessel then links := mitte+1 endwhile return "nicht gefunden"
In Ihrer Methode setzen Sie die lokale Variable links zunächst auf den Index des ersten Array-Elements, also auf den Wert 0. Die lokale Variable rechts setzen Sie auf den Index des letzten Array-Elements, also beispielsweise auf 99, wenn Ihr Array aus 100 Zahlen besteht. Sinnvoll ist es, eine dritte lokale Variable zu verwenden, welche die Rechenschritte in ihrer Methode zählt. Diese Variable schritte setzen Sie zu Beginn der Methode auf den Wert 0.
In der while-Schleife verfahren Sie dann genau so wie in dem Pseudo-Code; natürlich müssen Sie den Pseudo-Code in Java-Befehle umsetzen, der Pseudo-Code ist unter Java nicht lauffähig. Aus
if A[mitte] > Schluessel then rechts := mitte-1
wird bei dieser Umsetzung beispielsweise
if (liste[mitte] > suchzahl)
rechts = mitte-1;
Falls die Suchzahl nicht in dem Array enthalten ist, "returnen" Sie einfach die Zahl der Schritte, die notwendig waren, um zu diesem Ergebnis zu kommen.