Find the Start and End Indices of a Target in a Sorted Array

Medium20–25 min

Topics

ArrayBinary Search

Companies

AmazonMicrosoftGoogleBloomberg

Given an array nums sorted in non-decreasing order and an integer target, return the first and last index of target as a two-element array [start, end]. If target isn't present, return [-1, -1]. Solve it in O(log n) time — one binary search finds the leftmost matching index, another finds the rightmost.

Test Case 1:

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

Output:[3, 4]

Explanation:8 first appears at index 3 and last appears at index 4.

Test Case 2:

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

Output:[-1, -1]

Explanation:6 never appears in nums.

Test Case 3:

Input:nums = [1], target = 1

Output:[0, 0]

Explanation:A single matching element — start and end are the same index.

Constraints

◆1 ≤ nums.length ≤ 10⁴
◆-10⁴ ≤ nums[i], target ≤ 10⁴
◆nums is sorted in non-decreasing order (duplicates are allowed)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (sorted, comma-separated) — 1-12 integers, sorted ascending (duplicates OK)target

1	class Solution {
2	public int[] searchRange(int[] nums, int target) {
3	int lo = 0, hi = nums.length - 1, first = -1;
4	while (lo <= hi) {
5	int mid = lo + (hi - lo) / 2;
6	if (nums[mid] >= target) {
7	first = mid;
8	hi = mid - 1;
9	} else {
10	lo = mid + 1;
11	}
12	}
13	if (first == -1 \|\| nums[first] != target) {
14	return new int[]{-1, -1};
15	}
16	lo = 0;
17	hi = nums.length - 1;
18	int last = -1;
19	while (lo <= hi) {
20	int mid = lo + (hi - lo) / 2;
21	if (nums[mid] <= target) {
22	last = mid;
23	lo = mid + 1;
24	} else {
25	hi = mid - 1;
26	}
27	}
28	return new int[]{first, last};
29	}
30	}
31

↑lo

↑hi

Variables

lo0

hi3

first-1

INITIALIZE

First, binary search [0, 3] for the leftmost index where nums[i] ≥ 4.

Step 1 / 8

Approach & Solutions

Brute Force — Linear Scan

Brute

Walk the whole array once, remembering the first index where target shows up and continuously updating the last index every time it shows up again. Correct on any array, but it never uses the fact that equal values in a sorted array are always contiguous, which is what lets binary search jump straight to both ends.

TimeO(n)

SpaceO(1)

Java

Try it out

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;
                last = i;
            }
        }
        return new int[]{first, last};
    }
}

Optimal — Two Binary Searches

Optimal

Equal values in a sorted array sit in one contiguous block, so the answer is just its two edges. Binary-search once for the leftmost index with nums[i] ≥ target (the start, if it actually equals target), then binary-search again for the rightmost index with nums[i] ≤ target (the end).

TimeO(log n)