BudiBadu Logo

Find Target Range

Binary Search Medium 8 views
Like20

Find Target Range requires locating the first and last positions of a target value in a sorted integer array. If the target does not appear, return [-1, -1]. Because duplicates may exist, a single binary search for any occurrence is not enough; you must identify both boundaries precisely.

The standard solution runs two binary searches: one for the leftmost index where value equals target, and one for the rightmost index. Each search maintains strict boundary movement rules to avoid off-by-one errors. This keeps complexity at O(log n) and works cleanly for large arrays where linear scans would be unnecessary.

Judge cases include absent targets, empty arrays, single-element matches, and repeated runs where range length is greater than one. Output must be a two-integer array only. Correctness depends on careful comparison branching and post-search validation, especially when insertion-point style results do not actually contain the target. With consistent boundary handling, the function remains fast, deterministic, and robust across all sorted-input edge scenarios.

After locating potential boundaries, validate both indices against array bounds and target equality before returning. This prevents insertion-point artifacts from being mistaken as real matches when the target is absent. The final output must always be a two-element integer array under every branch.

Examples

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 - Budibadu
Recommendation Algorithm Flow for Find Target Range - Budibadu

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