Find First and Last Position — Dual Boundary Binary Search [LC 34, Google, Facebook]

Problem Statement#

Given a sorted array nums and a target value, return the starting and ending position of the target. If the target is not found, return [-1, -1].

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is sorted in non-decreasing order
• -10^9 <= target <= 10^9

Input:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Input:  nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Why This Problem Matters#

LC 34 is a classic FAANG binary search problem that specifically tests whether candidates can implement the two boundary variants of binary search without confusing them. Google and Facebook ask it regularly because it probes for precision: a working standard binary search is not enough — you need two separate searches that differ by a single character (< vs <= in the mid comparison).

The problem also introduces the concept of open-ended binary search ranges. Both left-boundary and right-boundary searches use hi = len(nums) (one past the last index) as the upper bound, allowing the result to land on this sentinel position, which unambiguously signals "not found."

Mastering this problem gives you the building blocks for dozens of harder problems: H-Index II (LC 275), Find K Closest Elements (LC 658), Minimum Number of Days to Make Bouquets (LC 1482), and any problem where you need to count elements satisfying a threshold.

The Core Insight#

Run two independent binary searches:

1. Left boundary — find the first index where nums[index] >= target. If that index is in range and nums[index] == target, the target exists starting there.
2. Right boundary — find the first index where nums[index] > target, then subtract 1. That gives the last occurrence.

The only difference between the two searches is the comparison direction:

• Left boundary: when nums[mid] < target, move lo right. When nums[mid] >= target, move hi left to mid.
• Right boundary: when nums[mid] <= target, move lo right. When nums[mid] > target, move hi left to mid.

Both use the open-ended range [0, n] and while lo < hi template, converging to a single index.

Visual Dry Run#

Input: nums = [5, 7, 7, 8, 8, 10], target = 8

Left-boundary search:

Left boundary = 3.

Right-boundary search:

Result: [3, 4]

Solution (Optimal)#

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def left_bound() -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if nums[mid] < target:
                    lo = mid + 1
                else:
                    hi = mid
            return lo
 
        def right_bound() -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if nums[mid] <= target:
                    lo = mid + 1
                else:
                    hi = mid
            return lo - 1
 
        left = left_bound()
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, right_bound()]

var searchRange = function(nums, target) {
    function leftBound() {
        let lo = 0, hi = nums.length;
        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
 
    function rightBound() {
        let lo = 0, hi = nums.length;
        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (nums[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo - 1;
    }
 
    const left = leftBound();
    if (left === nums.length || nums[left] !== target) return [-1, -1];
    return [left, rightBound()];
};

Time: O(log n) — two independent binary searches, each O(log n) Space: O(1) — only pointer variables used

Common Mistakes#

• Using hi = nums.length - 1 instead of hi = nums.length — the open-ended range is required so lo can settle on n when the target is greater than all elements.
• Confusing the two boundary searches — left boundary uses nums[mid] < target while right boundary uses nums[mid] <= target. Swapping them reverses the results.
• Forgetting to validate after the left-boundary search — if left == len(nums) or nums[left] != target, the target does not exist.
• Returning lo directly from the right boundary search without subtracting 1 — the right search finds the first index where nums[idx] > target, so the last valid index is lo - 1.
• Using a single standard binary search that returns on the first match — this gives neither boundary reliably.

Interview Tips#

• State explicitly that you will run two binary searches before coding — interviewers appreciate the clear decomposition.
• Explain the only difference between the two searches upfront: < vs <= in the mid comparison.
• After deriving left, add a guard before computing right — this avoids index errors on empty arrays or missing targets.
• Mention that Python's bisect.bisect_left and bisect.bisect_right implement exactly these two searches — useful for production code but write the explicit version in interviews.

Follow-up Questions#

• What if the array is unsorted? You must sort first (O(n log n)), then apply this. The binary search only works on sorted input.
• What is the count of occurrences? It is right - left + 1 once you have the boundaries. This is O(1) given the boundary indices.
• LC 35 (Search Insert Position) is the left-boundary search alone — where does target go if it is not found?
• Can you do it in one pass? One clever search can locate a boundary element and then expand, but two separate O(log n) searches are simpler and equally efficient.
• What if the array has billions of elements on disk? Use fractional cascading or an index structure, but the two-boundary decomposition still applies.

Key Takeaways#

• LC 34 is the definitive dual-boundary binary search problem; Google and Facebook use it to verify that candidates know both the left and right variants.
• Both boundary searches use hi = len(nums) (open-ended) so the result can reach the sentinel position n when the target is absent.
• The only difference between left and right boundary searches is < vs <= in the mid-value comparison — one character separates the two templates.
• After the left-boundary search, always validate: if left == n or nums[left] != target, return [-1, -1] immediately.
• The right-boundary result is lo - 1 (the search overshoots by one to find the first element greater than the target).
• Mastering this problem directly enables H-Index II (LC 275), Find K Closest Elements (LC 658), and all binary-search-on-answer problems with threshold counting.
• Use while lo < hi (not lo <= hi) to avoid an off-by-one when the search converges to a single candidate.