Know this before you start: “Find the first / last valid index (boundaries)”

Binary search for the first or last match

When the target appears several times, don't stop at the first hit: remember it and keep searching left (for the first) or right (for the last).

The idea

Plain binary search returns any matching index. Many problems want the boundary: the first position of a value, the last, or the first item ≥ x (the insert position).

Treat it as a search for where a condition switches from false to true: [F, F, F, T, T]. When mid is T, it might be the answer, so record it and search left; when it's F, search right.

See it step by step

First and last position of 8 in [5, 7, 7, 8, 8, 10]

First 8: mid = 2 (7) → right; mid = 4 (8) → record 4, go left; mid = 3 (8) → record 3, go left → first = 3
Last 8: mid = 2 (7) → right; mid = 4 (8) → record 4, go right; mid = 5 (10) → left → last = 4
Answer [3, 4].

In code (Python)

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] with ok(x) True, or hi + 1 if none."""
    answer = hi + 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if ok(mid):
            answer = mid
            hi = mid - 1        # maybe something earlier works too
        else:
            lo = mid + 1
    return answer

def search_range(nums, target):
    first = first_true(0, len(nums) - 1, lambda i: nums[i] >= target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    last = first_true(0, len(nums) - 1, lambda i: nums[i] > target) - 1
    return [first, last]

print(search_range([5, 7, 7, 8, 8, 10], 8))   # [3, 4]
print(search_range([5, 7, 7, 8, 8, 10], 6))   # [-1, -1]

O(log n) per boundary.

When you'll use it

First / last occurrence, insert position, count of a value in sorted data, “smallest index such that…”.

Common mistakes

Stopping at the first match.
Returning an index past the end without checking it.