LeetCode 34 – Find First and Last Position of Element in Sorted Array

Plain binary search finds an occurrence of a value. This problem wants the first and the last, and the honest way to get them is not to bolt a linear scan onto a binary search — that is O(n) the moment the array is all one value. The clean answer is one small primitive, lower bound, called twice.

The problem

Given a sorted array, return the first and last index of a target, or [-1, -1] if it is absent. Must be O(log n).

[5,7,7,8,8,10], target = 8  -> [3, 4]
[5,7,7,8,8,10], target = 6  -> [-1, -1]
[],             target = 0  -> [-1, -1]
[1,1,1,1,1],    target = 1  -> [0, 4]

That last case is the one that punishes the shortcut. Find any 1, then walk left and right to the ends — correct, and O(n). The O(log n) requirement exists specifically to rule it out.

Lower bound: one primitive, learned once

Rather than writing two nearly-identical searches with a boolean isLeft flag threaded through them, write one function that answers a slightly different question:

lower bound: the index of the first element >= target, or n if every element is smaller.

That single function gives both answers:

The first occurrence is lowerBound(target) — the first element not less than the target. Check that the value there actually equals the target; if it does not, the target is absent.
The last occurrence is lowerBound(target + 1) - 1 — the first element strictly greater than the target, minus one. That is exactly the last element equal to it.

No flag, no duplicated loop, and no second set of boundary conditions to get wrong. It is also a primitive worth owning outright: it is bisect_left in Python and std::lower_bound in C++, and it is the answer to a whole family of "first element satisfying X" problems.

The loop shape that makes it work

Lower bound uses a half-open window — hi starts at n, not n - 1, and the loop runs while lo < hi. That is not stylistic. The answer may legitimately be n when no element qualifies, and a window whose upper end maxes out at n - 1 cannot represent it.

Inside, there is no early return and no equality test. An element less than the target is definitely not the answer, so lo = mid + 1 discards it; anything else might be the answer, so hi = mid keeps it. The window shrinks every iteration, and when it is empty lo is the answer. Removing the == target case is what removes the bugs.

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = lowerBound(nums, target);

        if (first == nums.length || nums[first] != target) {
            return new int[] { -1, -1 };        // target is absent
        }

        // First index past the target, minus one, is the last occurrence.
        return new int[] { first, lowerBound(nums, target + 1) - 1 };
    }

    /** Index of the first element >= target, or nums.length if there is none. */
    private int lowerBound(int[] nums, int target) {
        int lo = 0, hi = nums.length;           // half-open: hi is exclusive

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            if (nums[mid] < target) {
                lo = mid + 1;                   // definitely not the answer
            } else {
                hi = mid;                       // might be the answer, keep it
            }
        }

        return lo;
    }
}

The first == nums.length check must come before nums[first], or an absent target larger than everything indexes out of bounds. Java's || short-circuits, so the order in that condition is load-bearing. It also covers the empty array for free: lowerBound returns 0, which equals nums.length.

One caveat on target + 1: it overflows if the target is Integer.MAX_VALUE. This problem bounds values at 10⁹ so it cannot happen, but if an interviewer removes that bound, write a separate upper-bound search rather than relying on the arithmetic.

Python

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        first = self._lower_bound(nums, target)

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

        return [first, self._lower_bound(nums, target + 1) - 1]

    def _lower_bound(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)          # half-open: hi is exclusive

        while lo < hi:
            mid = (lo + hi) // 2

            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid

        return lo

Python ships this as bisect.bisect_left and bisect.bisect_right, which reduce the whole problem to three lines. Name them — knowing the standard library is a plus — then write the loop, because the loop is what is being asked for.

Complexity

O(log n) time: two independent binary searches, and 2 · log n is still log n. O(1) space. Crucially this holds on [1,1,1,1,1], where the scan-outwards approach degrades to O(n) — construct that input yourself and say what it does to the naive version.

What the interviewer is checking

That you do not find one occurrence and then expand linearly.
That you factor out one primitive instead of writing two searches with a direction flag.
That the bounds check precedes the array access when the target is absent.
Empty array, single element, target smaller than everything, target larger than everything.
An array of one repeated value — the case the requirement exists for.
That you can state precisely what lower bound returns, including the n case.