Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

Basic Implementation

basic.c

#include <stdio.h>

int search(const int arr[], int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return search(arr, target, mid + 1, hi);
    return search(arr, target, lo, mid - 1);
}

int main(void) {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = (int)(sizeof(arr) / sizeof(arr[0]));
    int target = 11;
    printf("%d\n", search(arr, target, 0, n - 1));
    return 0;
}

Complexity

Time: O(log n)
Space: O(log n) call stack

Implementation notes

C stores the sorted input as a fixed local int arr[] = {1, 3, 5, 7, 9, 11, 13} and computes n with (int)(sizeof(arr) / sizeof(arr[0])) in main.
search(const int arr[], int target, int lo, int hi) receives the array as a pointer after parameter decay; const documents that recursive calls read but do not mutate the array.
The base case is if (lo > hi) return -1;, so -1 is the not-found sentinel. This trace does not hit that branch because target 11 is present.
Each call uses signed int bounds and mid = lo + (hi - lo) / 2, then either returns mid or tail-returns a narrower search call.
The trace starts with search(lo=0, hi=6), computes mid=3 with value 7, recurses right to (4, 6), then computes mid=5 with value 11 and returns 5.
printf("%d\n", search(arr, target, 0, n - 1)) prints the returned index. Visible memory is the stack array plus recursive stack frames and scalar parameters; there is no heap allocation.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.

cross-language comparison This C DSA version keeps the same data and final output as every other DSA book in this wave.