First and Last Position in a Sorted Array: Boundary Binary Search

Plain binary search answers "is the target here?" Interview questions almost never stop there. They ask for the first index holding the target, the last one, how many copies there are, or where the value would be inserted. All of those are the same small change to binary search: when you find a match, do not return. Record it as a candidate and keep shrinking towards the side you care about. What comes back is a boundary instead of an arbitrary match.

The problem it solves

Given a sorted array that may contain duplicates, such as [1, 3, 3, 3, 7, 9, 9, 11], return the first and last index of a target, or [-1, -1] if it is absent, in O(log n) time.

The classic binary search finds a 3, and which one depends on where the midpoints fall. Here the first midpoint is index 3, the last of the three. Two tempting fixes both fail the time limit in the worst case:

• Find any match, then walk left and right. If the whole array is the target, the walk is O(n).
• Linear scan. Correct and simple, and O(n) by definition.

The fix is to run binary search twice, each time hunting for a boundary.

The intuition

Think of the array as answering a yes/no question at every index, such as "is nums[i] at least the target?" Because the array is sorted, the answers are all "no" up to some point and all "yes" after it. The first "yes" is the boundary, and binary search finds it by halving the range while remembering the best "yes" seen so far:

• If nums[mid] qualifies, it might be the first one. Save mid as the answer, then search only to its left with hi = mid - 1, because an earlier index could also qualify.
• If it does not qualify, the boundary is to the right: lo = mid + 1.

When the range is empty, the saved answer is the leftmost qualifying index. The mirror image, "is nums[i] at most the target?", with the candidate saved and the search moved right, finds the last position.

So the first position of a target is first_at_least(target), provided the value there really equals the target, and the last position is last_at_most(target). The same boundary search, with a different question, solves insert position, the first bad version, and every "minimum value that works" problem.

Watch it run

The animation searches [1, 3, 3, 3, 7, 9, 9, 11] for the first value at least 3. There are three 3s, and plain binary search may return any of them; the goal is the first. nums[3] = 3 is at least 3, so it records index 3 as a candidate and keeps shrinking left, because an earlier 3 may exist. nums[1] = 3 also qualifies: record index 1, and shrink left again. nums[0] = 1 does not qualify; it is too small, and nothing at or before index 0 can be the boundary, so lo moves past it and the range is empty. The boundary is index 1. Never return on a hit: record it and keep going.

The code

The lesson's boundary search. It returns the first index whose value is at least the target, or -1 if none is:

def first_at_least(nums, target):
    lo, hi, answer = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            answer = mid          # a candidate...
            hi = mid - 1          # ...but look further left
        else:
            lo = mid + 1
    return answer

nums = [1, 3, 3, 3, 7, 9, 9, 11]
print(first_at_least(nums, 3))    # 1
print(first_at_least(nums, 4))    # 4   no 4: the first value above it
print(first_at_least(nums, 12))   # -1  nothing qualifies

Its mirror image finds the last index whose value is at most the target, and the two together answer the first-and-last question. The equality check matters: first_at_least for an absent value returns the next larger value's index:

def last_at_most(nums, target):
    lo, hi, answer = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            answer = mid          # a candidate...
            lo = mid + 1          # ...but look further right
        else:
            hi = mid - 1
    return answer

def search_range(nums, target):
    first = first_at_least(nums, target)
    if first == -1 or nums[first] != target:
        return [-1, -1]           # target is absent
    return [first, last_at_most(nums, target)]

print(search_range(nums, 3))      # [1, 3]
print(search_range(nums, 9))      # [5, 6]
print(search_range(nums, 4))      # [-1, -1]
print(search_range([], 4))        # [-1, -1]

Python's standard library already has both boundaries, known elsewhere as lower bound and upper bound. bisect_left returns the first index where the target could be inserted, which is the first value at least the target; bisect_right returns one past the last copy. Their difference counts occurrences:

from bisect import bisect_left, bisect_right

print(bisect_left(nums, 3), bisect_right(nums, 3))   # 1 4
print(bisect_right(nums, 9) - bisect_left(nums, 9))  # 2   occurrences of 9

All of it against a linear scan on 5,000 random sorted arrays full of duplicates, with targets below, inside and above the range:

import random

random.seed(21)
ok = True
for _ in range(5000):
    nums = sorted(random.randint(0, 9) for _ in range(random.randint(0, 15)))
    t = random.randint(-1, 10)
    hits = [i for i, v in enumerate(nums) if v == t]           # the linear scan
    ok &= search_range(nums, t) == ([hits[0], hits[-1]] if hits else [-1, -1])
    at_least = [i for i, v in enumerate(nums) if v >= t]
    ok &= first_at_least(nums, t) == (at_least[0] if at_least else -1)
    at_most = [i for i, v in enumerate(nums) if v <= t]
    ok &= last_at_most(nums, t) == (at_most[-1] if at_most else -1)
    ok &= bisect_right(nums, t) - bisect_left(nums, t) == len(hits)
print(ok)                         # True

The complexity

• Time: O(log n) per boundary, so two searches are still O(log n), even when every element equals the target.
• Space: O(1); the saved answer is one integer.
• Find-then-walk: O(log n + k) for k copies, which is O(n) when the array is mostly the target.

Where it goes wrong

• Returning on the first hit. That is plain binary search, and it returns whichever copy the midpoints land on.
• Forgetting the equality check. For an absent target, the first value at least the target is some other value.
• Mixing loop styles. The closed form here uses lo <= hi and hi = mid - 1; the half-open form uses lo < hi, hi = len(nums) and hi = mid. Mixing the two causes infinite loops or skipped elements.
• Moving the wrong pointer after a hit. For the first position move hi left; for the last position move lo right.
• Walking outward from a match. It passes small tests and degrades to O(n) on a long run of duplicates.

When it shows up in interviews

It is the standard follow-up to plain binary search and appears directly as "find the first and last position of an element" or "count occurrences in a sorted array". The same record-and-shrink loop drives binary search on the answer, where the yes/no question is "does this capacity work?", and find peak element. The whole family is listed on the patterns cheat sheet.

How to say it in an interview

"I'd run two boundary binary searches. For the first position, whenever nums[mid] is at least the target I save mid as a candidate and continue left with hi = mid - 1; otherwise I go right. When the range is empty the saved index is the leftmost value at least the target, and if it does not equal the target, the target is absent. For the last position I mirror it: save when nums[mid] is at most the target and continue right. Each search is O(log n) even if every element is the target, which walking outward from a match would not be. In Python, bisect_left and bisect_right give the same two boundaries."