Code Logo

Find Target Range

Published at05 Jan 2026
Created by
Medium 24 views
Like20

Given a sorted array of integers and a target value, return the first and last index where the target appears, as a two-element array [first, last]. If the target does not exist in the array, return [-1, -1].

Because the array is sorted, all copies of the target form one continuous block. The first index is the left edge of that block, and the last index is the right edge. Locating both edges requires two binary searches: one that finds the earliest position where the value is greater than or equal to the target, and one that finds the earliest position where the value is strictly greater than the target.

For example, if nums = [5,7,7,8,8,10] and target = 8, the answer is [3,4]. The left edge is 3 (the first 8) and the right edge is 4 (the last 8). If nums = [2,2,2,2,2] and target = 2, the answer is [0,4] because the entire array is the target block. If the target is absent, like target = 6 in the same array, the answer is [-1,-1].

This "find first and last occurrence" pattern is a common interview variant of binary search. It is used in range queries over sorted data, interval detection, and database index range scans. Mastering the two-boundary search makes it easy to solve related problems like counting occurrences (last - first + 1).

Edge cases include an empty array (return [-1,-1]), a single occurrence (both edges are the same index), the target spanning the entire array, and the target being smaller than all elements or larger than all elements (return [-1,-1]).

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

Solution Approach

Run two binary searches to find the left and right boundaries of the target block. First, find the left edge using nums[i] >= target; then verify the target actually exists there. If it does not, return [-1,-1]. Otherwise, find the right edge with a search for the first value strictly greater than the target, and subtract one.

function find_target_range(nums, target) {
  function findBound(first) {
    var left = 0, right = nums.length - 1, ans = -1;
    while (left <= right) {
      var mid = Math.floor((left + right) / 2);
      if (first) {
        if (nums[mid] >= target) { ans = mid; right = mid - 1; }
        else left = mid + 1;
      } else {
        if (nums[mid] > target) { ans = mid; right = mid - 1; }
        else left = mid + 1;
      }
    }
    return ans;
  }
  var first = findBound(true);
  if (first === -1 || nums[first] !== target) return [-1, -1];
  var last = findBound(false) === -1 ? nums.length - 1 : findBound(false) - 1;
  return [first, last];
}

The left-bound search records the candidate index whenever the value is at least the target, then keeps searching left. The right-bound search records the first index where the value is strictly greater than the target, so the last occurrence is one position before it.

Time complexity is O(log n), space complexity is O(1).

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;
    }
}