Hilfe bei Java-Programm Binäre Suche (Rekursiv)?
Ich habe ein iteratives JavaProgrogramm zur Binären Suche erstellt, welches nun in eine rekursive Form gebracht werden soll.
Zudem sollen Testfälle vorbereitet werden, in denen min. 5 verschiedene Folgen F nach Schlüsseln gesucht werden kann. Eine Folge soll die Länge 1, eine weitere die Länge 2 haben, die restlichensollen länger als 10 Elemente sein. Nach dem Start des Programms soll die i-te Folge per Tastatureingabe ausgewählt und ein Suchschlüssel eingegeben werden. Anschließend soll das Programm die Indexposition ausgeben oder melden, dass der Schlüssel nichtgefunden wurde.
Hier das Programm in iterativer Form:
public class BinarySearch {
public static void main(String[] args) {
new BinarySearch();
}
BinarySearch() {
int[] f = {0, 1, 2, 4, 5, 8, 9, 12, 13, 18};
int position = binarySearch(f, 5);
System.out.println("Schlüsseln 5an Postition: "+ position);
}
int NO_KEY = -1;
int binarySearch(int[] f, int key){
int i1 = 0, i2 = f.length - 1;
while (i1 <= i2){
int m = (i1 + i2) / 2;
if ( key == f [m]) {
return m;
}else if (key < f[m]){
i2= m - 1;
}else {
i1= m + 1;
}
}
return NO_KEY;
} }
1 Antwort
1. Ändere die Signatur von binarySearch():
int binarySearch(int[] f, int key, int i1, int i2)
Im Konstruktor musst Du sie jetzt mit binarySearch(f, 5, 0, f.length-1) aufrufen. Teste, ob noch alles tut.
2. Mache die Funktion rekursiv:
Abbruchkriterium: i1==i2. Hier gibst Du entweder f[i1] oder NO_KEY zurück.
Rekursion: m=(i1+i2)/2. Rufe binarySearch(f, key, i1, m) auf:
- Wenn das einen Treffer liefert, gib ihn zurück.
- Bei NO_KEY gib den Wert von binarySearch(f, key, m+1, i2) zurück.