Recursive decomposition and search invariants

The idea

A recursive function solves a smaller problem and combines its result. Specify a base case and a measure that decreases on every recursive path. Tracing only a successful middle-sized example can miss empty input or a branch that repeats the same state. Recursion also uses stack space; an iterative implementation may be more appropriate for very deep inputs.

Binary search illustrates a stronger invariant: in a sorted array, any remaining candidate lies inside a half-open interval [lo, hi). If the midpoint is too small, moving lo to mid plus one removes it; otherwise setting hi to mid keeps the possible first match. The interval length shrinks. The function below returns an insertion position, so reaching the array length is a meaningful result rather than an invalid index to dereference.

function lowerBound(a, x, lo = 0, hi = a.length) {
  if (lo === hi) return lo;
  const mid = lo + Math.floor((hi - lo) / 2);
  return a[mid] < x ? lowerBound(a, x, mid + 1, hi)
                    : lowerBound(a, x, lo, mid);
}
console.log(lowerBound([2, 4, 4, 9], 4));

1

The equality branch retains the midpoint and searches for an earlier equal value.