Implement Binary Search in Java using recursion.

To implement a basic recursive binary search in Java, you first need to define the method that takes the sorted array, the target value, and the indices defining the current search range. Here’s a simple implementation:

public class BinarySearch {
    public static int recursiveBinarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // Target not found
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // Target found
        }
        if (arr[mid] > target) {
            return recursiveBinarySearch(arr, target, left, mid - 1); // Search left half
        } else {
            return recursiveBinarySearch(arr, target, mid + 1, right); // Search right half
        }
    }
}

Explanation:

1. Base Case: If left exceeds right, the target is not in the array, returning -1.
2. Mid Calculation: mid is computed to find the middle index.
3. Target Comparison: The middle element is compared with the target. If they match, return mid.
4. Recursive Calls: Depending on whether the middle element is greater or less than the target, the search continues in the left or right half of the array.

Complexity:

• Time Complexity: O(log n)
• Space Complexity: O(log n) due to the recursion stack.

When implementing a recursive binary search, it’s essential to handle edge cases effectively. Consider scenarios where the array has only one element or where the target is not present. Here’s an improved version that addresses these cases:

public class BinarySearch {
    public static int recursiveBinarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // Target not found
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // Target found
        }
        // Handle edge case where only one element remains
        if (left == right) {
            return arr[left] == target ? left : -1;
        }
        if (arr[mid] > target) {
            return recursiveBinarySearch(arr, target, left, mid - 1);
        } else {
            return recursiveBinarySearch(arr, target, mid + 1, right);
        }
    }
}

Key Points:

• This version checks if left equals right to handle scenarios where only one element is left to check.
• It makes the implementation robust against various input cases, ensuring reliability.

Complexity:

• Time Complexity: O(log n)
• Space Complexity: O(log n) due to recursion.

While recursion is elegant for binary search, understanding the iterative approach is also valuable. Here’s how you might implement the iterative version:

public class BinarySearch {
    public static int iterativeBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid; // Target found
            }
            if (arr[mid] < target) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
        return -1; // Target not found
    }
}

Differences:

• The iterative approach avoids the overhead of recursive calls, making it more memory efficient in some cases.
• It uses a loop instead of recursion, which can be easier to understand for those less familiar with recursive logic.

Complexity:

• Time Complexity: O(log n)
• Space Complexity: O(1), as it uses a constant amount of space.