34. Find First and Last Position of Element in Sorted Array Medium

Given an array of integers 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]

Approach

Input: An integer array nums sorted in ascending order, and a target value.

Output: Return the starting and ending position of the target value in the array. If it doesn't exist, return [-1, -1].

This problem belongs to the Boundary Search category. The key is to use binary search to accurately locate the left and right boundaries of the target value.

We define a helper function lower_bound(nums, target) to find the index of the first element greater than or equal to target (i.e., the left boundary).

Specific steps are as follows:

Find the Left Boundary:
Call lower_bound(nums, target) to get the starting position start of the target value.
If start == nums.length (out of bounds) or nums[start] !== target, it means the target value does not exist, and we directly return [-1, -1].

Find the Right Boundary:
Call lower_bound(nums, target + 1) to find the first position greater than the target value, and subtract one to get the ending position end of the target value.

Return Result:
Return [start, end] which are the starting and ending positions of the target value.

Implementation

python

# Find the index of the first element greater than or equal to target (i.e., the left boundary)
def lower_bound(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            # If the middle value is less than the target, the target is in the right half
            left = mid + 1
        else:
            # If the middle value is greater than or equal to the target, it might be the answer, narrow the right boundary
            right = mid - 1
    
    # Finally, left points to the first position >= target
    return left


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # Find the first occurrence position of the target
        start = lower_bound(nums, target)

        # If start is out of bounds or the corresponding value is not the target, the target does not exist
        if start == len(nums) or nums[start] != target:
            return [-1, -1]

        # Find the first position >= target + 1, and subtract one to get the last position of the target
        end = lower_bound(nums, target + 1) - 1

        return [start, end]

javascript

const searchRange = function(nums, target) {
    /**
     * Binary search: Returns the first index greater than or equal to target
     * If the target exists, this is its starting position
     */
    function lowerBound(nums, target) {
        let left = 0;
        let right = nums.length - 1;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);

            if (nums[mid] >= target) {
                // Current value >= target, it might be the answer, continue searching to the left for smaller ones
                right = mid - 1;
            } else {
                // Current value < target, the answer must be on the right
                left = mid + 1;
            }
        }

        // Finally, left points to the first index >= target
        return left;
    }

    const start = lowerBound(nums, target);

    // If out of bounds, or nums[start] is not equal to the target value, it implies it doesn't exist
    if (start === nums.length || nums[start] !== target) {
        return [-1, -1];
    }

    // Find the first position >= target + 1, subtract 1 to get the last occurrence position of the target
    const end = lowerBound(nums, target + 1) - 1;

    return [start, end];
};

Complexity Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Links

34. Find First and Last Position of Element in Sorted Array (English)

34. 在排序数组中查找元素的第一个和最后一个位置 (Chinese)