Recursive Binary Search for Integers

Question

I have tried implementing the divide and conquer technique of binary search using recursion. The code for it can be seen below. I think when the program is run, I'm getting stack overflow. If anyone does manage to find a solution, I would greatly appreciate a reason for why this happens.

public class binarySearch{
    public static void main(String[] arguments){
        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
        int findNum = binSearch(array, 9, 0, array.length-1);
    }

    public static int binSearch(int[] array, int searchNum, int left, int right){
        int foundIndex = 0;
        boolean found = false;
        int mid = (right+left)/2;
        if(array[mid] == searchNum){
            found = true;
            foundIndex = mid;
        }
        else if(array[mid] > searchNum){
            right = mid;
            binSearch(array, searchNum, left, right);
        }
        else if(array[mid] < searchNum){
            left = mid;
            binSearch(array, searchNum, left, right);
        }

        if(found = true){
            return foundIndex;
        }
        else{
            return -1;
        }
    }
}

Answer 1

Your implementation logic is wrong and thus your code runs into infinite recursion. The correct code should be as follows -

public class binarySearch{
    public static void main(String[] arguments){
        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
        int findNum = binSearch(array, 9, 0, array.length-1);
    }

    public static int binSearch(int[] array, int searchNum, int left, int right){
        if(left>right)
            return -1; // We have now tried the full binary search and unable to find the element
        int mid = (right+left)/2;
        if(array[mid] == searchNum){
             return mid;
        }
        else if(array[mid] > searchNum)
            return binSearch(array, searchNum, left, mid-1); // <-- Here you were calling 
                                                             //binSearch(array, searchNum, left, right); which made your code go into infinite recursion

        else if(array[mid] < searchNum)
            return binSearch(array, searchNum, mid+1, right); //<-- you were calling 
                                                              //binSearch(array, searchNum, left, right); which made your code go into infinite recursion           
    }
}

The above code will return the index if the element is found in the array else it will return -1. You would also notice that I am directly returning the recursive call like - return binSearch(array, searchNum, mid+1, right);and not just calling like - binSearch(array, searchNum, left, right);

Hope this helps !