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)
    }
}