Binary search, written correctly

Binary search finds a target in a sorted array in O(log n) by discarding half the remaining range at every step. Twenty comparisons cover a million elements.

The algorithm is four lines. Getting the boundaries right is what people fail.

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;      // inclusive range [lo, hi]

  while (lo <= hi) {               // so the loop must use <=
    const mid = lo + ((hi - lo) >> 1);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

The four places it goes wrong

The range convention. Decide whether hi is inclusive or one past the end, then keep every line consistent. Inclusive hi pairs with while (lo <= hi) and hi = mid - 1. Exclusive hi pairs with while (lo < hi) and hi = mid. Mixing them gives an infinite loop or a missed element.

Overflow. (lo + hi) / 2 can overflow in fixed-width integer languages. lo + (hi - lo) / 2 cannot. It costs nothing to write it safely and interviewers notice.

Forgetting to move past mid. lo = mid instead of lo = mid + 1 means a two-element range never shrinks. This is the classic hang.

Assuming sorted input. Binary search on unsorted data returns nonsense, quietly. If you did not sort it yourself, say out loud that you are relying on the precondition.

Testing it properly

Four cases catch nearly every bug: empty array, single element (present and absent), target smaller than everything, target larger than everything. Then a two-element array, which is where the mid + 1 bug shows up.

Recursive form

const search = (a, target, lo = 0, hi = a.length - 1) => {
  if (lo > hi) return -1;
  const mid = lo + ((hi - lo) >> 1);
  if (a[mid] === target) return mid;
  return a[mid] < target
    ? search(a, target, mid + 1, hi)
    : search(a, target, lo, mid - 1);
};

Same complexity in time, but O(log n) stack space instead of O(1). Prefer the loop unless the recursion genuinely reads better.