Recursive Binary Search

Recursive binary search expresses the same divide and conquer strategy as binary search, but uses function calls instead of a loop. Each call reduces the search interval by half.

This form is closer to the mathematical definition of the algorithm, though it introduces call stack overhead.

Problem

Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that

$$ A[i] = x $$

If no such index exists, return $-1$.

Algorithm

Define a recursive function over a subarray $[l, r]$.

recursive_binary_search(A, x, l, r):
    if l > r:
        return -1

    m = l + (r - l) // 2

    if A[m] == x:
        return m
    else if A[m] < x:
        return recursive_binary_search(A, x, m + 1, r)
    else:
        return recursive_binary_search(A, x, l, m - 1)

Wrapper:

search(A, x):
    return recursive_binary_search(A, x, 0, length(A) - 1)

Example

Let

$$ A = [1, 4, 6, 8, 11, 15] $$

and

$$ x = 8 $$

Call sequence:

call	l	r	m	A[m]	result
1	0	5	2	6	recurse right
2	3	5	4	11	recurse left
3	3	3	3	8	found

Return index $3$.

Correctness

The recursion maintains the invariant:

• If $x$ exists in $A$, then it lies within the current interval $[l, r]$

Each recursive call reduces the interval size while preserving this invariant. When $l > r$, the interval is empty, so no valid index exists.

Complexity

case	time
best	$O(1)$
worst	$O(\log n)$
average	$O(\log n)$

Space complexity:

type	space
recursion stack	$O(\log n)$

Each recursive call adds one frame to the call stack.

Notes

• This version matches the divide and conquer structure directly.
• It is easier to reason about formally but less efficient in low level environments due to function call overhead.
• Tail recursion elimination may convert this to an iterative form in some compilers, but this is not guaranteed.

Implementation

def recursive_binary_search(a, x, l, r):
    if l > r:
        return -1
    m = l + (r - l) // 2
    if a[m] == x:
        return m
    elif a[m] < x:
        return recursive_binary_search(a, x, m + 1, r)
    else:
        return recursive_binary_search(a, x, l, m - 1)

func RecursiveBinarySearch(a []int, x int, l, r int) int {
    if l > r {
        return -1
    }
    m := l + (r-l)/2
    if a[m] == x {
        return m
    } else if a[m] < x {
        return RecursiveBinarySearch(a, x, m+1, r)
    } else {
        return RecursiveBinarySearch(a, x, l, m-1)
    }
}