I've been trying to learn algorithms and as part of this I have been trying to code binary search and the logic seems fine. The code doesn't terminate and the IDE stays idle forever. I don't understand what I'm doing wrong. Any help is appreciated. Thanks in advance!

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int no = 5;
        System.out.print(binSearch(arr, no, 0, arr.length - 1));


    }

    private static boolean binSearch(int[] arr, int no, int start, int end) {
        while(start <= end) {
            int mid = (start   end) / 2;
            if (arr[mid] == no) {
                return true;
            } else if (no > arr[mid]) {
                binSearch(arr, no, mid   1, end);
            } else if(no < arr[mid]) {
                binSearch(arr, no, start, mid - 1);
            }
        }
        return false;
    }
}

CodePudding user response：

You are missing the return on the two recursive calls:

private static bool binSearch(int[] arr, int no, int start, int end) {
    
    while(start <= end) {
        int mid = (start   end) / 2;
        if (arr[mid] == no) {
            return true;
        } else if (no > arr[mid]) {
            return binSearch(arr, no, mid   1, end);
        } else if(no < arr[mid]) {
            return binSearch(arr, no, start, mid - 1);
        }
    }
    return false;
}

You could also consider writing it in a non-recursive loop.

CodePudding user response：

okay so i think we review recursion a bit

binSearch(arr, num, start, end){

    while (start<=end){
        int mid = (start end)/2;
        if (arr[mid] == no) {
           return true              #when it finally matches return true 
        }


        else if (arr[mid] > no) {
            binSearch(arr, no, start, mid-1)  #call binSearch for new value

        }
    }
}

Just to illustrate recursion, imagine we want some value B for an input A. Now imagine a node or some point as an origin that represents our input A. For every point or node that follows after A is some step we take towards finding the value B.

Once we find the value that we want, the structure of our approach can be illustrated as a single graph with one direction. A --> C --> --> D --> B

That is essentially how recursion works. Now first, lets take a look at your else if statement. When your parameters meet one of the else if conditions you make a call to your binSearch method.

What this does is basically create a new point of origin rather than working off the initial one. So lets say at iteration number 3 you finally meet your boolean condition and it returns true. But where does it return true to?

Only the last call or the most recent call that was made to binSearch. Lets call it iteration 2.

Now once the return value is made it simply moves on to the next block of code which brings us to your while loop. The only way your code can move on to the next block of code (which is returning the false value), is to break out of the while loop, ie. have your start value be greater than your end value.

But remember, we are on iteration 2. And iteration 2 was given the values for start and end that satisfied the while-loop so it loops again and whatever else-if statement iteration 2 landed on before the final iteration that returned true, it will keep repeating indefinitely.

The obvious solution as mentioned above is to put 'return' before the call is made as that will return all the way back to the original call to binSearch.

Also, the while loop is not necessary unless you are doing it without recursion.