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 TypeScript DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

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

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

    1const arr: number[] = [1, 3, 5, 7, 9, 11, 13];2const target: number = 11;
    values this step0lo6hi11target

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

    7}8const mid = lo + Math.floor((hi - lo) / 2);9if (arr[mid] === target) {
    values this step3mid7arr[mid](4, 6)next call0lo6hi

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

    7}8const mid = lo + Math.floor((hi - lo) / 2);9if (arr[mid] === target) {
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    1const arr: number[] = [1, 3, 5, 7, 9, 11, 13];2const target: number = 11;
    values this step5stdout5result

Complexity

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

Implementation notes

  • TypeScript declares arr: number[] and target: number in outer scope. search(lo: number, hi: number): number passes only numeric bounds through recursive calls.
  • The base case lo > hi returns -1 as the miss sentinel. Otherwise each frame computes const mid = lo + Math.floor((hi - lo) / 2) and reads arr[mid].
  • The hit check uses strict equality, arr[mid] === target, and returns the index immediately. Numeric comparison arr[mid] < target recurses right with search(mid + 1, hi); the remaining branch recurses left.
  • Each recursive call creates a normal JavaScript stack frame after TypeScript compilation, carrying its own lo, hi, and mid values.
  • The replay starts at search(0, 6), computes mid=3 with arr[mid]=7, and recurses to (4, 6). The next frame computes mid=5, finds 11, and returns 5.
  • console.log(search(0, arr.length - 1)) prints 5. The array is not mutated or copied; visible allocation is the input number[], while the recursion uses call-stack state.