Frage von Kvanilli, 25

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;

} }

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von ralphdieter, 9

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.


Antwort
von PerfectMuffin, 15

"läufiges iteratives JavaProgrogramm"

Du machst mich kaputt

https://de.wikipedia.org/wiki/L%C3%A4ufigkeit <-- nsfw

Du hast es offensichtlich nicht einmal versucht, also mach deine Hausaufgaben alleine.

Sie kennen die Antwort?

Fragen Sie die Community