Recursive Binary Search Implementation in Java

Implement Binary Search in Java using recursion.

Certainly! Below is an implementation of the Binary Search algorithm in Java using recursion. This implementation assumes that the input array is sorted in ascending order.

public class BinarySearch {

    // Recursive method to perform binary search
    public static int binarySearch(int[] arr, int left, int right, int target) {
        // Base case: if the left index exceeds the right index, the target is not found
        if (left > right) {
            return -1; // Target not found
        }

        // Calculate the middle index
        int mid = left + (right - left) / 2;

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found
        }

        // If the target is smaller than mid, search in the left half
        if (target < arr[mid]) {
            return binarySearch(arr, left, mid - 1, target);
        }

        // If the target is larger than mid, search in the right half
        return binarySearch(arr, mid + 1, right, target);
    }

    // Helper method to initiate the binary search
    public static int search(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int target = 10;

        int result = search(arr, target);
        if (result == -1) {
            System.out.println("Element not found in the array.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Explanation:

1. binarySearch Method: This is the recursive method that performs the binary search. It takes the array, the left and right indices, and the target value as parameters.

   • If the left index exceeds the right index, it returns -1, indicating that the target is not found.
   • It calculates the middle index and checks if the target is equal to the middle element.
   • If the target is less than the middle element, it recursively searches the left half of the array.
   • If the target is greater than the middle element, it recursively searches the right half of the array.

2. search Method: This is a helper method that initializes the left and right indices and calls the binarySearch method.

3. main Method: This is the entry point of the program where an example array and target value are defined. It calls the search method and prints the result.

Usage:

You can run this code in any Java environment. Just make sure to modify the arr and target variables in the main method to test with different inputs.