0

I am trying to create a binary search algorithm using recursion in Java, when debugging everything seems to be okay up until it finds the value and should return the index of the key needed. However, for some reason it skips the return statement and goes to the bottom return statement.

public int binSearch(int key, int L, int R) {

    int mid =(R + L)/2;

    if (R < L) {
        return -1;
    }

    if (A[mid] == key) {
        return mid;
    }

    if (key > A[mid]) {
        binSearch(key, mid + 1, R);
    }

    if (key < A[mid]) {
        binSearch(key, L, mid - 1);
    }
   return -1;
}
  • Think about what happens when your call to `binSearch(key, L, mid - 1);` returns back from the recursion. Instead of using what was returned by that function call you are returning `-1` down at the bottom. So instead you should probably say `return binSearch(...)` for each call. Also your if statements already check for all cases of comparing `key` to `A[mid]`. You would probably benefit from using `if else` and `else` conditions when checking these comparisons. – Karl Oct 16 '18 at 15:36
  • You are missing the return statement. Try this way **return binSearch()** – suvojit_007 Oct 16 '18 at 15:47

2 Answers2

1

I was able to salvage this from an old post. I know it doesnt fix your problem, but it shows you another way to solving this problem.

public static int binarySearch(int[] a, int target) {
    return binarySearch(a, 0, a.length-1, target);
}

public static int binarySearch(int[] a, int start, int end, int target) {
    int middle = (start + end) / 2;
    if(end < start) {
        return -1;
    } 

    if(target==a[middle]) {
        return middle;
    } else if(target<a[middle]) {
        return binarySearch(a, start, middle - 1, target);
    } else {
        return binarySearch(a, middle + 1, end, target);
    }
}
B. Cratty
  • 1,725
  • 1
  • 17
  • 32
0

You are missing some return statements (when you are invoking binSearch recursively)

public int binSearch(int key, int L, int R) {
    int mid =(R + L)/2;
    if (R < L) {
        return -1;
    }
    if (A[mid] == key) {
        return mid;
    }
    if (key > A[mid]) {
        return binSearch(key, mid + 1, R);
    }
    if (key < A[mid]) {
        return binSearch(key, L, mid - 1);
    }
    return -1;
}