Lower bound, upper bound and duplicates

Plain binary search answers "is it here?". Most real questions are boundary questions: where would this go, how many are below it, what is the first element at least this large. With duplicates, plain binary search returns an index, not the one you wanted.

Lower bound

The first index whose value is ≥ target — the insertion point that keeps the array sorted.

function lowerBound(sorted, target) {
  let lo = 0;
  let hi = sorted.length;          // exclusive: an answer of length means "past the end"

  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);

    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid;                 // mid might be the answer, so keep it
  }

  return lo;
}

Note the shape: no =<mark> target check, no early return. The loop narrows until lo </mark>= hi, and that meeting point is the answer. This template is worth memorising as-is — it is the one you adapt for everything else.

Upper bound

The first index whose value is > target. Identical, with <= in the comparison:

const upperBound = (sorted, target) => {
  let lo = 0, hi = sorted.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (sorted[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
};

What the pair gives you

const first = lowerBound(a, x);
const last = upperBound(a, x);

first === last;              // x is absent
last - first;                // how many copies of x
a.slice(first, last);        // every copy

Counting occurrences in a sorted array is therefore O(log n), not O(n). "First and last position of an element in a sorted array" — a standard interview question — is exactly this pair.

Related shapes

• Search in a rotated sorted array: one half is always sorted; decide which, then recurse into the half that can contain the target.
• Find the peak / minimum in a rotated array: compare mid against hi and discard the sorted half.
• Search a 2D matrix sorted row-wise and column-wise: start at the top-right corner and walk left or down, O(n + m).