I Tried to do Binary Search In Java, but its Not Returning the the correct Value. But Prints the Right one.

public class ReBinarySearch {
        public static int rec_binarysearch(int[] array,int search, int first, int last){
            if(array.length == 0){
                return -1;
            }
            int mid= first   (last - first)/2;
            if(first<=last){
                if(array[mid] == search ){
                    System.out.println(mid);
                    System.out.println("FOUND At Index " mid); //Printing this Value.
                   return mid; //Not returning this Value
                }
                else if(array[mid] > search){
                rec_binarysearch(array, search, first, mid-1 );
                     }else if(array[mid] < search){
                            rec_binarysearch(array, search, mid 1, last);
                         }
                }
            return -1; //Always Returning this Value
        }
    public static void main(String args[]){
        int[] array={0,1,2,3,4,5,6,7,8,9,10};
        int search=10;
       System.out.println(rec_binarysearch(array, search, 0, array.length-1));
     
    }
}

Binary search is not returning the value as expected the code above. but its printing the Solution Right. what I need is to return that Value into main function.

CodePudding user response：

Your function rec_binarysearch is a recursive function, which is calling itself. But at the points where you call it recursively, you just ignore the return value. Thus you need to return the value from the function itself inside of the function. I only need to add two return statements and your code works:

public class ReBinarySearch {
    public static int rec_binarysearch(int[] array, int search, int first, int last) {
        if (array.length == 0) {
            return -1;
        }
        int mid = first   (last - first) / 2;
        if (first <= last) {
            if (array[mid] == search) {
                System.out.println(mid);
                System.out.println("FOUND At Index "   mid); //Printing this Value.
                return mid; //Not returning this Value
            } else if (array[mid] > search) {
                return rec_binarysearch(array, search, first, mid - 1);
            } else if (array[mid] < search) {
                return rec_binarysearch(array, search, mid   1, last);
            }
        }
        return -1; //Always Returning this Value
    }

    public static void main(String args[]) {
        int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int search = 10;
        System.out.println(rec_binarysearch(array, search, 0, array.length - 1));
    }
}

Your code can further be optimized to the following:

public static int rec_binarysearch(int[] array, int search, int first, int last) {
    //// base cases/termination points should come first:
    // terminate if the array is empty
    if (array.length == 0) {
        return -1;
    }
    // terminate if first is greater than last.
    if (first > last) {
        return -1;
    }
    // terminate if search was found
    int mid = first   (last - first) / 2;
    if (array[mid] == search) {
        return mid; //Not returning this Value
    }

    //// recursive cases:
    // if none of the above was true we can continue 
    // searching with the recursive calls...
    if (array[mid] > search) {
        return rec_binarysearch(array, search, first, mid - 1);
    } else { // (array[mid] < search) is always true at this point
        return rec_binarysearch(array, search, mid   1, last);
    }
}

I applied the best practice in there, that a recursively called function should always begin with the base cases (termination points). Meaning, we should always start the function with handling the cases, in which the recursion should stop and exit the function. In your case the following needs to be checked:

• is the array empty?
• is (first > last)? this is especially important, because your recursive calls increase the value of first and decrease the value of last. So if you try to find a value in an array that doesn't contain the search value, you will run into this case.
• did you find a match?

Edit

To make the function 100% correct, you would also need to check, that first and last are not out of range. But in that case it would be better to have another function that does these checks (as well as array.length ==0) and then calls the recursive function to retrieve the result.