Code Logo

Find Target Range

Published at05 Jan 2026
Created by
Medium 10 views
Like20

You are given a sorted array and a target value. The job is to return the first index where the target appears and the last index where it appears.

If the target does not exist in the array at all, the answer should be [-1,-1]. Because the array is sorted, all copies of the same target will appear in one continuous block.

For example, if nums = [5,7,7,8,8,10] and target = 8, the answer is [3,4]. If nums = [2,2,2,2,2] and target = 2, the answer is [0,4] because the whole array is the target block.

So the task is to locate both edges of the target's block in the sorted array.

Example Input & Output

Example 1
Input
nums = [5,7,7,8,8,10], target = 8
Output
[3,4]
Explanation

The target 8 first appears at index 3 and last at index 4.

Example 2
Input
nums = [2,2,2,2,2], target = 2
Output
[0,4]
Explanation

All elements are equal to the target, so it spans from index 0 to 4.

Example 3
Input
nums = [5,7,7,8,8,10], target = 6
Output
[-1,-1]
Explanation

The target 6 does not exist in the list.

Algorithm Flow

Recommendation Algorithm Flow for Find Target Range
Recommendation Algorithm Flow for Find Target Range

Solution Approach

The standard way to solve this is to run two binary searches.

The first search finds the left boundary: the first position where nums[i] >= target. The second search finds the first position where nums[i] > target. Once you have that, the right boundary is one step before it.

In other words:

left = lowerBound(target)
right = lowerBound(target + 1) - 1

Or more generally, the second search looks for the first value strictly greater than the target.

After finding left, you still need to check whether the target actually exists there. If left is out of range or nums[left] !== target, then the answer is [-1,-1].

This keeps the whole solution at O(log n) time with O(1) extra space.

Best Answers

java
import java.util.Arrays;

class Solution {
    public int[] find_target_range(int[] nums, int target) {
        int first = findBound(nums, target, true);
        if (first == -1) return new int[]{-1, -1};
        int last = findBound(nums, target, false);
        return new int[]{first, last};
    }

    private int findBound(int[] nums, int target, boolean isFirst) {
        int l = 0, r = nums.length - 1;
        int bound = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                bound = mid;
                if (isFirst) r = mid - 1;
                else l = mid + 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return bound;
    }
}