Binary Search (Recursive)

Problem Statement

Implement binary search recursively: given a sorted array nums and a target, return its index or -1 if absent.

Example

Input:  nums = [1,3,5,7,9], target = 7
Output: 3

Approach

The recursive form mirrors the iterative one. Compute the middle; if it matches, return it; otherwise recurse into the left half (left..mid-1) or the right half (mid+1..right). The base case is left > right, meaning the target is not present.

Complexity

• Time: O(log n)
• Space: O(log n) recursion stack

Solution Code

Python

def binary_search(nums, target, left=0, right=None):
    if right is None:
        right = len(nums) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search(nums, target, mid + 1, right)
    else:
        return binary_search(nums, target, left, mid - 1)

Java

int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) return binarySearch(nums, target, mid + 1, right);
    else return binarySearch(nums, target, left, mid - 1);
}

C++

int binarySearch(vector<int>& nums, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) return binarySearch(nums, target, mid + 1, right);
    else return binarySearch(nums, target, left, mid - 1);
}

Key Takeaways

• Recursion is elegant but adds O(log n) stack frames versus the iterative O(1).
• Tail-recursive calls can be optimised to a loop by some compilers.
• Reference: LeetCode 704 (Binary Search); CLRS, Ch. 2 (divide and conquer).