Find first and last positions of an element in a sorted array

In a sorted list where a number can repeat, find where its run of copies starts and where it ends.

Simple way: time O(n)
room O(1)
Clever way: time O(log n)
room O(1)

The problem, simply

You get an array sorted from small to big, and a target number. The target may appear many times in a row, once, or not at all.

Return two positions: the first index where the target appears and the last index where it appears. If it is not there, return [-1, -1].

A story to remember it

Picture it

arraysorted

The 5s form one run from index 1 to index 4. We want both ends of that run.

answer

Examples

A normal case

In: nums = [5, 7, 7, 8, 8, 10], target = 8
Out: [3, 4]

The 8s sit at index 3 and 4.

A long run

In: nums = [2, 5, 5, 5, 5, 7, 9], target = 5
Out: [1, 4]

Four copies in a row. The walkthrough finds both ends.

Not there

In: nums = [5, 7, 7, 8, 8, 10], target = 6
Out: [-1, -1]

6 would sit between 5 and 7, but it is missing.

Everything is the target

In: nums = [3, 3, 3], target = 3
Out: [0, 2]

The run is the whole array.

Empty array

In: nums = [], target = 1
Out: [-1, -1]

Nothing to search. The code must not crash.

Way 1: the simple way

Walk from left to right. The first time you see the target, write down its index as first. Every time you see it, write down its index as last.

java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) first = i;   // the first copy we meet
                last = i;                     // keeps moving to the latest copy
            }
        }
        return new int[] { first, last };
    }
}

How long it takes: one walk over the array, O(n). Extra room: O(1).

Way 2: the clever way

Run binary search twice. A normal binary search stops when it finds the target. Here we do not stop: we write the spot down and keep searching on one side.

Search 1 (first copy):

lo = 0, hi = n - 1, first = -1.
If nums[mid] == target, write first = mid, then search left: hi = mid - 1.
If nums[mid] < target, search right. If bigger, search left.

Search 2 (last copy) is the same, except when you find the target you write last = mid and search right: lo = mid + 1.

Two binary searches that keep going after a hit

01 / 11

arraysorted

Search 1 finds the first 5. lo = 0, hi = 6. No answer yet.

target: 5
first: -1

checking
done
answer
ignored

java

class Solution {
    private int find(int[] nums, int target, boolean wantFirst) {
        int lo = 0, hi = nums.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                ans = mid;                       // best so far
                if (wantFirst) hi = mid - 1;     // maybe another copy on the left
                else lo = mid + 1;               // maybe another copy on the right
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }

    public int[] searchRange(int[] nums, int target) {
        return new int[] { find(nums, target, true), find(nums, target, false) };
    }
}

How long it takes: two binary searches, each O(log n). Even a run of a million copies takes about 20 peeks per search. Extra room: O(1).

Watch out for

(lo + hi) / 2 can overflow for huge arrays. Use lo + (hi - lo) / 2.
Forgetting the empty array. With hi = -1 the loop never runs and both answers stay -1, which is correct.
Mixing up which pointer moves on a hit: left end means hi = mid - 1, right end means lo = mid + 1.

What interviewers ask next

How many times does the target appear? last - first + 1, or 0 if it is missing. This is the GeeksforGeeks "number of occurrences" problem.
Can you do it with one helper? Yes: write lowerBound(x), the first index with a value at least x. Then first = lowerBound(target) and last = lowerBound(target + 1) - 1, after checking that first really holds the target.
What if the array is sorted but rotated? Find the rotation point first, then search the right half.
Where would the target be inserted to keep the array sorted? That is exactly lowerBound(target) (LeetCode 35).

Remember this

Grown-up words: the jumping game is binary search, the first copy is the lower bound, one past the last copy is the upper bound, and the run of copies is the range of equal elements.