Find First and Last Position: Two Binary Searches

Find First and Last Position of Element in Sorted Array is LeetCode 34, and it is one of the best problems for learning how binary search can do more than just find a single match. A basic binary search finds some occurrence of the target, but it cannot tell you whether that occurrence is the first or the last. This problem forces you to control which direction the search collapses toward. Once you learn that trick, you have two reusable building blocks that show up in many other problems.

The problem

You are given an array of integers nums sorted in non-decreasing order. Find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example: nums = [5, 7, 7, 8, 8, 10], target = 8. The answer is [3, 4] because the first 8 is at index 3 and the last 8 is at index 4.

Example: nums = [5, 7, 7, 8, 8, 10], target = 6. The answer is [-1, -1] because 6 does not appear in the array.

The visual makes the idea concrete: in a sorted array, all copies of the target sit in a contiguous block. You need the left edge and the right edge of that block.

Why two binary searches

A single binary search can land on any copy of the target. If the array is [8, 8, 8, 8, 8] and you binary search for 8, you hit the middle element. But you have no idea whether that is the first, the last, or somewhere in between.

The fix is to run binary search twice with different tie-breaking rules:

1. Left-biased search: when you find the target at mid, do not stop. Collapse the right boundary (hi = mid) so the search keeps moving left. This converges on the first occurrence.
2. Right-biased search: when you find the target at mid, do not stop. Collapse the left boundary (lo = mid) so the search keeps moving right. This converges on the last occurrence.

Each search is still O(log n), and you run two of them, so the total is O(log n).

Visual walkthrough

Let's trace both searches on nums = [5, 7, 7, 8, 8, 10] with target = 8.

Two searches, each taking at most 4 steps on a 6-element array. Both are O(log n). Together they give us the full range [3, 4].

The code

Here is the complete Python solution for LeetCode 34:

def searchRange(nums, target):
    def find_first(nums, target):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def find_last(nums, target):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if nums[mid] > target:
                hi = mid - 1
            else:
                lo = mid
        return lo

    if not nums:
        return [-1, -1]

    first = find_first(nums, target)
    if nums[first] != target:
        return [-1, -1]

    last = find_last(nums, target)
    return [first, last]

Let's break down each piece.

find_first uses lo < hi as the loop condition. When nums[mid] < target, the first occurrence must be to the right, so lo = mid + 1. When nums[mid] >= target, the first occurrence is at mid or to the left, so hi = mid. Notice hi = mid, not hi = mid - 1. If nums[mid] equals the target, mid might be the first occurrence. You cannot skip it.

The midpoint in find_first is lo + (hi - lo) // 2, which rounds down. When lo and hi are adjacent (hi = lo + 1), mid equals lo. Since the else branch sets hi = mid, the range shrinks. No infinite loop.

find_last flips the logic. When nums[mid] > target, the last occurrence is to the left, so hi = mid - 1. When nums[mid] is at most the target, the last occurrence is at mid or to the right, so lo = mid.

The midpoint in find_last is lo + (hi - lo + 1) // 2, which rounds up. This is critical. If you round down when using lo = mid, you get an infinite loop when lo and hi are adjacent. Rounding up guarantees mid = hi in that case, so hi = mid - 1 shrinks the range.

The outer function calls find_first first. If nums[first] does not equal the target, the target is not in the array at all, so return [-1, -1]. Otherwise, call find_last and return both results.

Complexity analysis

Time: O(log n). Each binary search runs in O(log n). Two searches means 2 * O(log n), which is still O(log n).

Space: O(1). Only a handful of variables: lo, hi, mid, first, last. No extra data structures.

The building blocks

This problem is built on two core building blocks:

Left-biased binary search. The standard binary search template, modified so that when nums[mid] matches the target, you collapse rightward (hi = mid) instead of returning. This finds the first (leftmost) occurrence of a value.

Right-biased binary search. The mirror image: when nums[mid] matches, you collapse leftward (lo = mid) and round the midpoint up to avoid infinite loops. This finds the last (rightmost) occurrence.

# Left-biased (find first):
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid

# Right-biased (find last):
while lo < hi:
    mid = lo + (hi - lo + 1) // 2
    if nums[mid] > target:
        hi = mid - 1
    else:
        lo = mid

These two templates are reusable far beyond this problem. Any time you need to find the boundary where a condition flips in a sorted array, one of these applies. Problems like "find the first element greater than X" or "find the last element less than X" are just variations of the same idea.

Edge cases to watch for

• Target not found: nums = [5, 7, 7, 8, 8, 10], target = 6. find_first converges on index 0 or some other index where nums[lo] != target. Return [-1, -1].
• Single element, target present: nums = [8], target = 8. Both searches converge on index 0. Return [0, 0].
• Single element, target absent: nums = [5], target = 8. find_first converges on index 0, nums[0] != 8. Return [-1, -1].
• All elements are the target: nums = [8, 8, 8, 8], target = 8. find_first converges on index 0, find_last converges on index 3. Return [0, 3].
• Target at the left edge: nums = [8, 9, 10], target = 8. find_first returns 0, find_last returns 0. Return [0, 0].
• Target at the right edge: nums = [5, 7, 8], target = 8. find_first returns 2, find_last returns 2. Return [2, 2].
• Empty array: nums = []. The guard clause returns [-1, -1] immediately.

From understanding to recall

The idea is clean: run binary search twice, biasing left then right. You understand it after one read.

But in an interview, the details will bite you. Was it hi = mid or hi = mid - 1 for the left-biased search? Do you round up or round down in find_last? Is the condition nums[mid] < target or nums[mid] != target? One wrong choice and the code either misses the answer, returns an off-by-one result, or loops forever.

Spaced repetition fixes this. You type both helper functions from scratch today, again tomorrow, then in three days. By the fourth repetition, the asymmetry between find_first and find_last (round-down vs. round-up, hi = mid vs. lo = mid) is locked in muscle memory. You are not re-deriving it under pressure. You just know.

LeetCode 34 is a perfect SRS candidate because the code is short but the boundary details are easy to mix up. Nail both templates once, and biased binary search stops being a source of bugs.

Related posts

• Binary Search: More Than Finding a Number - The foundational binary search pattern that this problem builds on
• Find Peak Element (LeetCode 162): Binary Search on Slope - Another binary search variant that uses lo < hi with hi = mid to converge on a single answer