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

Basic Implementation

basic.js
Replay: real traced execution (multi-file project)
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 11;

function search(lo, hi) {
  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 = [1, 3, 5, 7, 9, 11, 13];2const target = 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 = [1, 3, 5, 7, 9, 11, 13];2const target = 11;
    values this step5stdout5result

Complexity

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

Implementation notes

  • JavaScript stores arr as a const Array of Number values and keeps target in the outer scope; recursive calls pass only the numeric lo and hi bounds.
  • The base case lo > hi returns -1. Otherwise the frame computes const mid = lo + Math.floor((hi - lo) / 2), reads arr[mid], and uses strict equality for the hit check.
  • Numeric comparison arr[mid] < target chooses search(mid + 1, hi) for the right half; the remaining branch returns search(lo, mid - 1) for the left half. Each recursive call creates a normal JavaScript stack frame and returns the found index back to the caller.
  • The replay starts with search(lo=0, hi=6), computes mid=3 with arr[mid]=7, and recurses right to (4, 6). The next frame computes mid=5, sees arr[mid]=11, and returns 5.
  • console.log(search(0, arr.length - 1)) prints the numeric result 5. The search does not mutate or copy the array; it uses call-stack frames for recursion, and the only lesson-visible heap allocation is the input array.