A sorted audit log of HTTP status codes. Compliance wants the first and last index of 500 so they can slice the incident window. The first version found any 500 with a binary search, then walked left and right until the run ended. A burst of a million identical codes turned that walk into a linear scan of the whole log.

Find First and Last Position asks for two bound searches. An array already gives a[i] for free. A full walk uses that and still pays O(n). The sort is the license to discard; a run of duplicates is not a license to walk.

This is an interview writeup, not a procedure lecture. The binary search post owns lower bound, upper bound, and why they use a half-open hi. The membership writeup returns an equal index and stops. That loop is the wrong halt for this prompt.

The problem

Given a non-decreasing int[] nums and an int target, return the first and last indices where nums[i] == target. If the target is absent, return [-1, -1]. Typical interviews want O(log n) time even when the target fills most of the array.

nums = [2, 4, 4, 6, 6, 9], target = 6  →  [3, 4]
nums = [2, 4, 4, 6, 6, 9], target = 5  →  [-1, -1]
nums = [3],                 target = 3  →  [0, 0]

Note: Membership that returns on the first equal mid is correct for “is it here?” It is not the leftmost, and it is not the rightmost. Do not reuse that return as one end of the range.

Linear scan is the honest brute force

Walk once, record the first hit, keep updating the last. Correct. Linear.

int[] searchRangeScan(int[] nums, int target) {
    int first = -1;
    int last = -1;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            if (first < 0) {
                first = i;
            }
            last = i;
        }
    }
    return new int[] { first, last };
}

Finding any equal index with membership and walking outward is the same bill when every slot equals target. At n in the millions you paid a run-length walk for a question two bound searches answer in a handful of probes: where does the equal run start and end?

Two half-open searches: lower bound, then upper bound

Lower bound is the first i with nums[i] >= target (or n). Upper bound is the first i with nums[i] > target. If lower bound is n or nums[left] != target, return [-1, -1]. Else the closed range is [left, upperBound - 1]. Do not return on equality: lower bound shrinks left (hi = mid), upper bound shrinks right (lo = mid + 1). Half-open hi = n so the answer may sit past the last slot.

nums = [2, 4, 4, 6, 6, 9]   target = 6
        0  1  2  3  4  5

lowerBound (first >= 6)
lo=0 hi=6 mid=3  6 stays   → hi=3
lo=0 hi=3 mid=1  4<6       → lo=2
lo=2 hi=3 mid=2  4<6       → lo=3
lo=3 hi=3  left = 3

upperBound (first > 6)
lo=0 hi=6 mid=3  6<=6      → lo=4
lo=4 hi=6 mid=5  9>6       → hi=5
lo=4 hi=5 mid=4  6<=6      → lo=5
lo=5 hi=5  last = 4

The Java is those two loops:

int[] searchRange(int[] nums, int target) {
    int left = lowerBound(nums, target);
    if (left == nums.length || nums[left] != target) {
        return new int[] { -1, -1 };
    }
    int right = upperBound(nums, target) - 1;
    return new int[] { left, right };
}

int lowerBound(int[] a, int target) {
    int lo = 0;
    int hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int upperBound(int[] a, int target) {
    int lo = 0;
    int hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

Time is O(log n) — two searches, each throwing away half the remaining range. Space is O(1). Off-by-one and the JDK miss encoding already live on the algorithms post; do not re-lecture them unless they ask.

Note: Bound searches keep mid a candidate (hi = mid). Membership’s inclusive lo <= hi plus hi = mid never terminates when lo == hi. Bound searches use hi = n and lo < hi. Arrays.binarySearch does not promise the leftmost duplicate.

What interviewers usually poke next

  • Count only. upperBound - lowerBound. No need to materialize both indices.
  • Insert position if missing. Lower bound is that index. This prompt asked for [-1, -1] on a miss.
  • Unsorted input. Discarding a half is a lie. They still asked for indices.
  • Empty / null. Lower bound returns 0, the left == n check fires, [-1, -1]. In production you would reject null; at the board, ask.

You are done with this problem when you can say, out loud, why the linear scan is correct, why walking out from a membership hit is worst-case linear, and why equality shrinks left for the first index and right for the last.