Red and blue on a closed interval

Almost every engineer has experienced the quiet dread of writing binary search. The high-level concept is simple: divide the array in half, inspect the middle, discard one side. But when you write the code, the doubts pile up. Is it left < right or left <= right? Should updates be mid + 1 or mid? When duplicate values appear, do you return left, right, or left - 1?

Most people tweak +1s and <=s until tests pass. Instead of guessing, let’s step through what actually happens.

Finding the first 8

Look at a concrete array with duplicate values:

nums = [5, 6, 7, 8, 8, 10]

Suppose we want the index of the first 8. That should be index 3.

Step through the search below:

Follow the pointers as you step forward:

• We begin with left = 0 and right = 5. The midpoint lands on index 2 (value 7). Since 7 < 8, it turns red. left advances to index 3.
• Now left = 3 and right = 5. The midpoint lands on index 4 (value 8). A textbook search with if (nums[mid] == target) return mid would stop right here and return 4, giving you the second 8. Instead, this search marks it blue and pulls right inward to index 3.
• The midpoint lands on index 3 (value 8). It is also blue, so right pulls inward to index 2.
• At left = 3 and right = 2, the search terminates. left points squarely at index 3.

It found the exact first 8. But don’t worry about why the pointer updates work just yet.

Now find the last 8

What if the requirement flips? We don’t want the first 8 anymore. We want the last 8 (index 4 in this array, or index 8 in an array with five copies of 8).

The moment you try to adapt the code, everything gets slippery:

• If nums[mid] == 8, you want to search right, so you might try left = mid. But in integer division, (left + right) / 2 rounds down. When left = 4 and right = 5, mid = 4. If nums[4] == 8, left stays 4. The loop never terminates.
• If you fix the rounding by adding 1 before dividing, your pointer formulas are no longer symmetric.
• When the loop exits, does left hold the answer? Or right? Or left - 1?

There is a subtle difference between finding the first occurrence and finding the last occurrence. How do we handle this difference with confidence, without rewriting binary search from scratch every time?

The monotonic predicate

The breakthrough is realizing that binary search does not care about numbers, sorted arrays, or duplicates.

Binary search only cares about a monotonic predicate: a boolean test P(x) that returns false for every element up to some boundary, and true from that boundary all the way to the end:

[ false, false, false | true, true, true ]

We paint every cell where the predicate is false Red, and every cell where it is true Blue:

[   Red,   Red,   Red | Blue, Blue, Blue ]

Every binary search problem in existence collapses into the same task: locate the boundary where the color flips from Red to Blue.

• To find the first 8: ask “Is this number >= 8?” Numbers < 8 are false (Red). Numbers >= 8 are true (Blue). The first 8 is the first blue cell.
• To find the last 8: ask “Is this number > 8?” Numbers <= 8 are false (Red). Numbers > 8 are true (Blue). The last 8 sits directly before the first blue cell—it is the last red cell.

The invariant on a closed interval

To see why this works, strip away the numbers completely. Look at pure booleans:

We defend this partition using a closed interval [left, right]:

• [0, left - 1] is confirmed Red (false).
• [right + 1, n - 1] is confirmed Blue (true).
• [left, right] is the uninspected window where the color is still unknown.

Initially, nothing has been inspected, so left = 0 and right = n - 1. The confirmed red and blue zones start empty.

In each iteration, we evaluate P(nums[mid]):

• If P(nums[mid]) is false (Red), we expand the confirmed red zone: left = mid + 1.
• If P(nums[mid]) is true (Blue), we expand the confirmed blue zone: right = mid - 1.

Both updates are strictly symmetric. Both exclude mid. Neither pointer can ever stall in place.

When does the loop terminate? When left > right. The uninspected interval has shrunk to zero width. The red prefix and the blue suffix now touch.

Because [0, left - 1] is all Red and [right + 1, n - 1] is all Blue:

• left is guaranteed to be the first blue cell (first true).
• left - 1 is guaranteed to be the last red cell (last false).

The code: one loop to rule them all

Because every search is finding the partition boundary, you only ever need one binary search function:

function lowerBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1; // Red: expand left boundary
    } else {
      right = mid - 1; // Blue: shrink right boundary
    }
  }

  return left; // First blue cell
}

The condition while (left <= right) means: “is there still at least one uninspected cell?” When the loop exits, left sits squarely on the first blue cell.

Reusing the model: the last 8

Now we return to our second puzzle: finding the last 8.

Instead of writing a new while loop or fighting with left = mid, we ask: which predicate puts all the 8s in the red zone?

“Is this number > 8?”

For integers, the first element > 8 is the first element >= 9. We run lowerBound(nums, 9). When lowerBound finishes, left lands on the first element strictly greater than 8 (the first blue cell).

Where is the last 8? Directly to the left of left—at left - 1, the last red cell!

Step through the player above. Notice how left lands at index 9 (value 11, the first element > 8). The last 8 sits at left - 1 (index 8).

All that remains in code is a bounds check:

function lastIndexOf(nums: number[], target: number): number {
  const i = lowerBound(nums, target + 1) - 1;
  if (i < 0 || nums[i] !== target) return -1;
  return i;
}

The four boundary queries

Every standard boundary query in a sorted array is just reading either the first blue cell or the last red cell from this single template:

Off-by-one errors disappear because the pointers are physical fences guarding known regions, not guesses. One loop, one invariant, every search variation answered.