Here is a sorted array with duplicate values: [1, 2, 2, 2, 2, 3, 5, 7]. You need the FIRST occurrence of 2.

You have the exact-match binary search from the previous lesson — the one that works perfectly on arrays with unique elements. It finds the target, returns its index, done. It has never failed you.

But what happens when the target appears more than once? The search will find a 2, but which one? Index 1? Index 3? It depends on where mid happens to land, which depends on the array length and the arithmetic of floor division. The result is essentially arbitrary.

Walk through the exact-match template on [1, 2, 2, 2, 2, 3, 5, 7] with target 2:

// lo=0, hi=7 → mid=3, arr[3]=2 === target → return 3

One comparison. Returns index 3. The correct answer is index 1. The search found a 2 — just the wrong one. And the exact-match template has no mechanism to realize its mistake. The moment it sees arr[mid] === target, it returns. There is no “keep looking leftward” logic.

This is not an edge case you can patch with a post-search linear scan. If the array has 100,000 copies of 2, the first occurrence could be anywhere in that run. The whole point of binary search is avoiding linear scans. You need a template that narrows to the boundary — the exact position where the value changes from “less than target” to “equal to target.”

Try it and see which 2 the exact-match template lands on.

The exact-match search found a 2 — but not the first one. It landed on index 3 when the answer is index 1. The problem is not a bug in the usual sense. The template is working exactly as designed — it just was not designed for this question.

Now you need to figure out what to do differently. The key decision happens when arr[mid] === target. The exact-match template says “stop, you found it.” But for first-occurrence, finding a match is not the end — it is a clue that the answer might be further left.

At each step, you will decide how the pointers move. Make the wrong choice and you will see exactly what breaks. Make the right choice and the search will converge on the first occurrence.

function search(arr, target) {

  let lo = 0, hi = arr.length - 1;

  while (lo <= hi) {

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === target) return mid;  // ← returns ANY match

    if (arr[mid] < target) lo = mid + 1;

    else hi = mid - 1;

  }

  return -1;

}

After piloting the pointers manually, you will assemble the boundary template from code tiles. The critical tile is hi = mid — not hi = mid - 1. That single difference is what keeps the matching element as a candidate instead of discarding it.

You just discovered the core tension in binary search: when you find a value that matches, should you stop or keep going?

In the exact-match template (lo <= hi, mid +/- 1, return mid on match), you stop immediately. That is correct when you want ANY occurrence — but it is wrong when you want the FIRST.

In the boundary template (lo < hi, hi = mid), you keep going. When arr[mid] >= target, mid is a candidate — it might be the answer, but there could be an earlier one. Setting hi = mid (not mid - 1) keeps that candidate alive while narrowing leftward.

The subtle difference between lower_bound and upper_bound is which side mid goes to when it matches:

• Lower bound (arr[mid] >= target): hi = mid — mid could be the first match, search left
• Upper bound (arr[mid] > target): hi = mid — but arr[mid] <= target sends lo = mid + 1, pushing past equal elements

Here is the pattern in code:

// Lower bound: first index where arr[i] >= target

function lowerBound(arr: number[], target: number): number {

  let lo = 0, hi = arr.length;

  while (lo < hi) {

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] < target) lo = mid + 1;

    else hi = mid;   // arr[mid] >= target: keep mid alive

  }

  return lo;

}

// Upper bound: first index where arr[i] > target

function upperBound(arr: number[], target: number): number {

  let lo = 0, hi = arr.length;

  while (lo < hi) {

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] <= target) lo = mid + 1;  // push past equals

    else hi = mid;

  }

  return lo;

}

Same template structure. Different predicate boundary. Different convergence point. The only line that changes is the condition: < vs <=. And the count of any element is simply upperBound - lowerBound.

Walk through both on [1, 2, 2, 2, 2, 3, 5, 7] with target 2:

// lowerBound: finds first index where arr[i] >= 2

// lo=0, hi=8, mid=4: arr[4]=2 >= 2 → hi=4

// lo=0, hi=4, mid=2: arr[2]=2 >= 2 → hi=2

// lo=0, hi=2, mid=1: arr[1]=2 >= 2 → hi=1

// lo=0, hi=1, mid=0: arr[0]=1 < 2  → lo=1

// lo=1, hi=1 → return 1  ✓ (first occurrence)

// upperBound: finds first index where arr[i] > 2

// lo=0, hi=8, mid=4: arr[4]=2 <= 2 → lo=5

// lo=5, hi=8, mid=6: arr[6]=5 > 2  → hi=6

// lo=5, hi=6, mid=5: arr[5]=3 > 2  → hi=5

// lo=5, hi=5 → return 5  ✓ (first index PAST all 2s)

//

// Count of 2s: upperBound - lowerBound = 5 - 1 = 4 ✓

This is LC 34 (Find First and Last Position of Element in Sorted Array) — one of the most commonly asked binary search problems. The first position is lowerBound(target) and the last position is upperBound(target) - 1. If lowerBound equals upperBound, the target is not present.

The same boundary technique powers LC 35 (Search Insert Position) — which is just lowerBound by another name — and LC 2300 (Successful Pairs of Spells and Potions), where you binary search the boundary in a sorted array of potions for each spell. Once you can write both bounds, you can answer any “how many elements satisfy X in a sorted range” question in O(log n).