Binary Search Recursion

Problem Statement

Write a Java program that implements a recursive binary search algorithm to find the index of a target element in a sorted array of integers. The program should return the index of the target if found, or -1 if the target does not exist in the array. Test the program with arrays containing both existing and non-existing elements. You can visualize this as searching for a word in a dictionary by repeatedly opening to the middle page and narrowing the search to one half of the book.

Input: A sorted array of integers and a target integer (e.g., arr = [1, 3, 5, 8, 9], target = 5). Output: An integer representing the index of the target in the array, or -1 if the target is not found (e.g., 2 for target 5). Constraints:

• The array length is between 0 and 10^5.
• Elements are integers between -10^9 and 10^9.
• The array is sorted in ascending order.
• The target may or may not exist in the array. Example:
• Input: arr = [1, 3, 5, 8, 9], target = 5
• Output: 2
• Explanation: The target 5 is found at index 2 in the sorted array.
• Input: arr = [1, 3, 5, 8, 9], target = 7
• Output: -1
• Explanation: The target 7 is not present in the array.

Pseudocode

FUNCTION binarySearch(arr, target, left, right)
    IF arr is null OR left > right THEN
        RETURN -1
    ENDIF
    SET mid to (left + right) / 2
    IF arr[mid] equals target THEN
        RETURN mid
    ELSE IF arr[mid] < target THEN
        RETURN binarySearch(arr, target, mid + 1, right)
    ELSE
        RETURN binarySearch(arr, target, left, mid - 1)
    ENDIF
ENDFUNCTION

FUNCTION mainBinarySearch(arr, target)
    RETURN binarySearch(arr, target, 0, length of arr - 1)
ENDFUNCTION

Algorithm Steps

1. Check if the input array is null or if the left index exceeds the right index, indicating an empty search space. If so, return -1.
2. Define a recursive helper function that takes the array, target, and left and right indices as parameters.
3. In the recursive function, calculate the middle index of the current search space.
4. Compare the element at the middle index with the target. If they are equal, return the middle index.
5. If the middle element is less than the target, recursively search the right half of the array (from mid + 1 to right).
6. If the middle element is greater than the target, recursively search the left half of the array (from left to mid - 1).
7. In the main function, initiate the recursion by calling the helper function with the initial left index as 0 and the right index as the array length minus 1.
8. Return the result from the recursive function, which is either the target’s index or -1 if not found.

Java Implementation

public class BinarySearchRecursion {
    // Main method to initiate recursive binary search
    public int binarySearch(int[] arr, int target) {
        // Check for null array
        if (arr == null) {
            return -1;
        }
        // Call recursive helper with initial boundaries
        return binarySearchHelper(arr, target, 0, arr.length - 1);
    }

    // Helper method for recursive binary search
    private int binarySearchHelper(int[] arr, int target, int left, int right) {
        // Base case: empty search space or invalid indices
        if (left > right) {
            return -1;
        }
        // Calculate middle index
        int mid = left + (right - left) / 2;
        // If target found at mid, return index
        if (arr[mid] == target) {
            return mid;
        }
        // If target is greater, search right half
        else if (arr[mid] < target) {
            return binarySearchHelper(arr, target, mid + 1, right);
        }
        // If target is smaller, search left half
        else {
            return binarySearchHelper(arr, target, left, mid - 1);
        }
    }
}

Output

For the input arr = [1, 3, 5, 8, 9], target = 5, the program outputs:

2

Explanation: The target 5 is found at index 2 in the sorted array.

For the input arr = [1, 3, 5, 8, 9], target = 7, the program outputs:

-1

Explanation: The target 7 is not present in the array.

For an empty array arr = [], the program outputs:

-1

Explanation: An empty array contains no elements, so the target cannot be found.

How It Works

• Step 1: The binarySearch method checks if the array is null. For [1, 3, 5, 8, 9], it is valid, so it calls the helper function with left = 0 and right = 4.
• Step 2: In binarySearchHelper:
  • First call: left = 0, right = 4, mid = 2, arr[2] = 5. Since 5 equals the target, return 2.
  • For target 7: First call: mid = 2, arr[2] = 5 < 7, recurse on left = 3, right = 4.
  • Second call: mid = 3, arr[3] = 8 > 7, recurse on left = 3, right = 2.
  • Third call: left > right, return -1.
• Example Trace: For [1, 3, 5, 8, 9] with target 5:
  • Check mid = 2, arr[2] = 5, matches target, return 2.
  • For target 7: Check mid = 2, arr[2] = 5 < 7, recurse on right half [8, 9]. Check mid = 3, arr[3] = 8 > 7, recurse on left half (empty). Return -1.

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(log n), as the algorithm halves the search space with each recursive call.
• Space complexity: O(log n) due to the recursive call stack, which grows logarithmically with the array size.
• Best case: O(1) if the target is at the midpoint of the first call.
• Average and worst cases: O(log n) for up to log n recursive calls.

✅ Tip: Use recursive binary search for sorted arrays to leverage its O(log n) efficiency, and test with both existing and non-existing targets to ensure correctness. Use the formula left + (right - left) / 2 for midpoint calculation to avoid integer overflow.

⚠ Warning: Binary search requires a sorted array; applying it to an unsorted array will produce incorrect results. Ensure proper bounds checking to avoid infinite recursion or ArrayIndexOutOfBoundsException.