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;
        }
    }
}

Have you tried using a debugger to see how its behavior differs from what you expected? — Scott Hunter, Jun 05 '20 at 19:35

score 2 · Answer 1 · answered Jun 05 '20 at 20:23

All of the solution posted so far has a integer overflow problem while calculating mid.The same bug lurked in JDK for more than 20 years https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

int binarySearch(int arr[],int searchNum,int left, int right)
    {
        if (right >= left) {
            int mid = (left+right)>>>1; 
            if (arr[mid] == searchNum)
                return mid;
            if (arr[mid] > searchNum)
                return binarySearch(arr, left,mid - 1, searchNum);

            return binarySearch(arr, mid + 1, right, searchNum);
        }
        return -1;
    }

user · Answer 2 · 2020-06-05T20:31:42.027

0

You're calling binSearch but never returning the value of that call. I think you're trying to treat found as a static variable in C, but there's no such thing in Java. Even if you modify it in another stackframe, the value in your current stackframe will still stay false.

A better way would be to use tail-recursion and directly return the result.

public static int binSearch(int[] array, int searchNum, int left, int right){
    if (left == right) 
        return -1;
    int mid = (right + left) >>> 1;
    if(array[mid] == searchNum) 
        return mid;
    else if(array[mid] > searchNum) 
        return binSearch(array, searchNum, left, mid);
    else 
        return binSearch(array, searchNum, mid + 1, right);
}

And you can invoke the method like this (right should be exclusive)

int findNum = binSearch(array, -1, 0, array.length);

EDIT: After reading the answer by Debapriya Biswas, I changed the line int mid = (right + left) / 2; to int mid = (right + left) >>> 1; to avoid failing when right + left is greater than the max value of int.

edited Jun 05 '20 at 20:31

answered Jun 05 '20 at 19:36

user

7,435
3
14
44

What happens if left=0, right=1, searchNum=1, array[0]=0, and array[1]=1? – Scott Hunter Jun 05 '20 at 19:40
@ScottHunter My bad, didn't realize OP was calling it with `array.length - 1`. I've added that to my answer now – user Jun 05 '20 at 19:42
Shouldn't it be `left > right ` to confirm element isn't in the array – Abhishek Bhagate Jun 05 '20 at 19:50
@Abhishek No, I've modified how the method is supposed to be called. right is exclusive, so left will never exceed it. – user Jun 05 '20 at 20:26

Abhishek Bhagate · Accepted Answer · 2020-06-05T19:46:54.733

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 !

The recursive calls are equivalent to `binSearch(array, searchNum, mid-1, mid)` and `binSearch(array, searchNum, mid, mid+1)`; that doesn't seem correct. — Scott Hunter, Jun 05 '20 at 19:42
What is the point of changing `left` or `right` before a recursive call? — Scott Hunter, Jun 05 '20 at 19:46

Recursive Binary Search for Integers

3 Answers3