Searching

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.ts 
const arr: number[] = [1, 3, 5, 7, 9, 11, 13];
const target: number = 11;

function search(lo: number, hi: number): number {
  if (lo > hi) {
    return -1;
  }
  const mid = lo + Math.floor((hi - lo) / 2);
  if (arr[mid] === target) {
    return mid;
  }
  if (arr[mid] < target) {
    return search(mid + 1, hi);
  }
  return search(lo, mid - 1);
}

console.log(search(0, arr.length - 1));

Complexity

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

Implementation notes

  • Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
  • The final output is intentionally small and deterministic for cross-language comparison.
execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.
cross-language comparison This TypeScript DSA version keeps the same data and final output as every other DSA book in this wave.