Implement Recursive Binary Search in Java

Binary search is an efficient searching algorithm that works by dividing a sorted array into two parts and repeatedly searching in the part where the target element can possibly be found. It works on the principle of divide and conquer and has a time complexity of O(log n).

In this blog, we will discuss the implementation of binary search using recursion in Java.

Recursive Binary Search in Java:

Lets jump to the code directly:

public class BinarySearchRecursive {
    public static final int NOT_FOUND = -1;
    /*
     * Performs the standard binary search using two comparison per level.
     * This is a driver that calls the recursive method
     * @return index where item is found, or NOT_FOUND
     */
    public static int binarySearch(Comparable[] a, Comparable x) {
        return binarySearch(a, x, 0, a.length - 1);
    }
    /*
     * Hidden recursive method
     */
    private static int binarySearch(Comparable[] a, Comparable x, int low, int high) {
        if (low > high) 
          return NOT_FOUND;
      
        int mid = (low + high) / 2;
        if (a[mid].compareTo(x) < 0) 
          return binarySearch(a, x, mid + 1, high);
        else if (a[mid].compareTo(x) > 0) 
          return binarySearch(a, x, low, mid - 1);
        else 
          return mid;
    }
    // Test program
    public static void main(String[] args) {
        int SIZE = 8;
        Comparable[] a = new Integer[SIZE];
        for (int i = 0; i < SIZE; i++) 
          a[i] = new Integer(i * 2);
        for (int i = 0; i < SIZE; i++) 
          System.out.println("Found " + i + " at " + binarySearch(a, new Integer(i)));
    }
}

Above program will give output as below:

Now, lets see what we did above:

Above Java code implements a recursive binary search algorithm to find the index of an element x in a sorted array a. Here is a step-by-step breakdown of how the code works:

1. The code defines a class called BinarySearchRecursive.

2. It defines a constant NOT_FOUND which is set to -1.

3. It defines a public method called binarySearch which takes in two arguments - an array of Comparable objects called a and a Comparable object called x. This method serves as a driver method for the recursive binarySearch method (defined later in the code).

4. The binarySearch method calls the recursive binarySearch method and passes it four arguments - the array a, the object x, the starting index 0, and the ending index a.length - 1.

5. The code defines a private recursive method called binarySearch which takes in four arguments - the array a, the object x, the starting index low, and the ending index high.

6. The recursive binarySearch method checks if low is greater than high. If it is, then it means that x is not present in the array and the method returns the NOT_FOUND constant.

7. If low is not greater than high, the method calculates the middle index mid as the average of low and high.

8. The method then checks if the object at mid in the array is less than x. If it is, then it recursively calls binarySearch with mid + 1 as the new starting index and high as the ending index.

9. If the object at mid in the array is greater than x, then the method recursively calls binarySearch with low as the starting index and mid - 1 as the new ending index.

10. If the object at mid in the array is equal to x, then the method returns mid as the index where the object is found.

11. The code defines a main method which creates an array of SIZE integers and populates it with even numbers. It then calls binarySearch on each element of the array and prints out the index where the element is found.