Binary search (recursive implementation)

Challenge

Search a sorted array for a value using recursion.

Task

Implement int bsearch_rec(const int *a, int lo, int hi, int target) that returns an index of target in the sorted array a, searching the half-open range [lo, hi), or -1 if target is not present in that range.

Input

• a: an int array sorted in non-decreasing order (read-only).
• lo: inclusive lower bound of the search range.
• hi: exclusive upper bound of the search range.
• target: the value to find.

Output

int: an index i in [lo, hi) with a[i] == target, or -1 if absent. If several elements equal target, any matching index is acceptable.

Example

a = {1, 3, 5, 7, 9}
bsearch_rec(a, 0, 5, 5)   ->   2
bsearch_rec(a, 0, 5, 1)   ->   0
bsearch_rec(a, 0, 5, 9)   ->   4
bsearch_rec(a, 0, 5, 10)  ->   -1

Edge cases

• An empty range (lo == hi) returns -1.
• Single-element range.
• Target outside the array's value range returns -1.

Rules

• Must be recursive (the function calls itself); O(log n).
• Compute the midpoint as lo + (hi - lo) / 2, not (lo + hi) / 2, to avoid integer overflow on large indices.

Why this matters

Binary search is the canonical divide-and-conquer algorithm. The recursive form is shorter; the iterative form is fractionally faster (no stack frames). Implementing both is a rite of passage for every C developer.

Input format

Sorted int array a; half-open range [lo, hi); target.

Output format

int: an index of target, or -1 if absent.

Constraints

a is sorted array of ints; lo and hi define half-open search range [lo, hi).

Starter code

int bsearch_rec(const int *a, int lo, int hi, int target) { /* TODO */ return -1; }

Common mistakes

Integer overflow in (lo + hi) / 2 or infinite recursion on boundary updates.

Edge cases to handle

lo >= hi (empty range), target at a[lo], target at a[hi-1], target not in array.

Complexity

O(log n) time, O(log n) stack space.

Background lessons

• Recursion — base case + smaller subproblem
• Searching

Up next

• Binary search
• Merge sort