Binary search (recursive implementation)

Challenge

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

• a is sorted in non-decreasing order.
• lo and hi are inclusive/exclusive respectively.
• If multiple equal values match target, any valid index is acceptable.

Examples

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

Constraints

• Must be recursive (your function calls itself).
• O(log n).
• Use lo + (hi - lo) / 2 instead of (lo + hi) / 2 to avoid integer overflow on large indices.

Edge cases

• Empty range (lo == hi) → return -1.
• Single-element range.
• Target outside the array's value range.

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, half-open range [lo, hi), target value.

Output format

Index of target or -1.

Constraints

Recursive only. O(log n).

Starter code

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

Common mistakes

Using (lo + hi) / 2 — overflow when lo + hi > INT_MAX. Going off-by-one on the range (mixing inclusive and exclusive bounds).

Edge cases to handle

Empty range; single element; target absent; duplicates.

Complexity

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

Background lessons

• Recursion — base case + smaller subproblem
• Searching

Up next

• Binary search
• Merge sort