Compile Zeitfehler in Binary Search rekursive Implementierung

Question

Ich bin ein Übersetzungsfehler rekursiv in binärer Such Implementierung immer

Hier ist meine Methode:

public static int binarySearch(int[] a, int start, int end, int x) { 
    if (start > end) { 
     return -1; 
    } 
    int mid = (start + end)/2; 
    if (a[mid] == x) { 
     return mid; 
    } else if (a[mid] > x) { 
     binarySearch(a, start, mid - 1, x); 
    } else { 
     binarySearch(a, mid + 1, end, x); 
    } 
} 

Ich gebe zwei Basisfall für diese und die Rückkehr zwei int Werte, aber immer noch bekomme ich Fehler, warum das passiert. Irgendwelche verwandten Gedanken würden geschätzt werden.

Dank

Answer 1

Was denken Sie beim ersten Aufruf zurückgegeben wird, wenn sowohl start > end und a[mid] == xfalse sind?

Sie benötigen eine rekursive Aufrufe und zurück, so dass der gefundene Wert (oder -1) wird durch die Rekursion Stack-Frames propagieren zurück:

public static int binarySearch(int[] a, int start, int end, int x) { 
    if (start > end) { 
     return -1; 
    } 
    int mid = (start + end)/2; 
    if (a[mid] == x) { 
     return mid; 
    } else if (a[mid] > x) { 
     return binarySearch(a, start, mid - 1, x); // return here 
    } else { 
     return binarySearch(a, mid + 1, end, x); // return here 
    } 

} 

Answer 2

binarySearch(a, start, mid - 1, x);UND In Ihren Aussagen binarySearch(a, mid + 1, end, x);, sind Sie gerade Aufruf der Funktion binarysearch. Statt dessen müssen Sie die Ausgabe dieser rekursiven Aufrufe zurückgeben.

also der richtige Weg, dies zu tun ist returnbinarySearch(a, start, mid - 1, x);zu verwenden undreturnbinarySearch(a, mid + 1, end, x);