寻找有序数组中特定元素起止位置

Problem

Given an integer array nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

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

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

Example 3: Input: nums = [], target = 0 Output: [-1,-1]

Idea

Use binary search twice. First, find the first occurrence of target: - If nums[mid] >= target, move the right pointer left. - Otherwise, move the left pointer right. - This finds the leftmost position where target could appear.

Then, find the last occurrence of target: - If nums[mid] <= target, move the left pointer right. - Otherwise, move the right pointer left. - This finds the rightmost position where target could appear.

If target does not exist, return [-1, -1].

Time complexity: O(log n), Space complexity: O(1)

Pseudo-code

FindRange(nums, target) {
    first = search left until the first target is found;
    last = search right until the last target is found;

    if target does not exist {
        return [-1, -1];
    }

    return [first, last];
}