Binary search function not working

Question

I'm new to Java and am just beginning to learn some simple data structures and algorithms. I've been trying to implement a binary search function but I keep getting a stack overflow error and I don't know where it's coming from.

public class BinarySearch {
    public static void main (String[]args){
        BinarySearch bs = new BinarySearch();

    int array [] = {1, 8, 6, 91, 52, 74, 5, 9};
    int length = array.length;
    bs.sort(array, 0, length-1);
    bs.print(array);
    System.out.println();
    System.out.println(bs.binarySearch(array, 0, length-1, 5));
}

public int binarySearch(int array [], int low, int high, int desired){
    int pivot = array[(low+high)/2];
    if(desired<pivot){
        binarySearch(array,low,pivot, desired);
    }else if(desired>pivot){
        binarySearch(array, pivot+1, high, desired);
    }else {
        return (low+high)/2;
    }
    // if element not present in array
    return -1;
}

Answer 1

Your code has several problems.

1. You aren't returning the result of the recursive call. Add return.

   if(desired<pivot){
       return binarySearch(...);
   }else if(desired>pivot){
       return binarySearch(...);
   }
   

2. Don't mix the index you're checking with the pivot value you're checking. Calculate the index and use it separately. Also, use index - 1 instead of index as the high when recurring low, to eliminate the current index from future consideration.

   int index = (low+high)/2;
   int pivot = array[index];
   
   if(desired<pivot){
       return binarySearch(array,low,index - 1, desired);
   }else if(desired>pivot){
       return binarySearch(array, index+1, high, desired);
   }else {
       return index;
   }
   

3. If your low value is greater than your high value, the value wasn't found. That is your base case, not returning -1 at the bottom (which is now unreachable code anyway, because every branch of logic above returns a value already). Place it above your current if.

   int index = (low+high)/2;
   int pivot = array[index];
   if (low > high)
       return -1;
   if ...
   

Assuming your sort works properly, the above changes should return the index of the element properly, or -1 if not found.