# Recursive Binary Search

# 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]$.

```id="x3k9p1"
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:

```id="k29d8f"
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

```id="z7c1m9"
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)
```

```id="v4n8s2"
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)
    }
}
```