Searching

Binary Search (Recursive)

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

Algorithm

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.

Basic Implementation

basic.c
Replay: real traced execution (multi-file project)
#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;
}

  1. lo ← 0, hi ← 6, target ← 11

    1#include <stdio.h>
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    4if (lo > hi) return -1;5int mid = lo + (hi - lo) / 2;6if (arr[mid] == target) return mid;
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    4if (lo > hi) return -1;5int mid = lo + (hi - lo) / 2;6if (arr[mid] == target) return mid;
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    14int target = 11;15printf("%d\n", search(arr, target, 0, n - 1));16return 0;
    values this step5stdout5result

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.