Practice/Meta/Leetcode 34. Find First and Last Position of Element in Sorted Array

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

CodingMust

Problem

You are given a sorted array of integers arranged in non-decreasing order and a target integer value. Your task is to find the starting and ending positions of the target value within the array.

If the target value appears in the array, return a two-element array containing the first index and last index where the target appears. If the target is not found in the array, return [-1, -1].

Your algorithm must run in O(log n) time complexity, where n is the length of the array.

Requirements

1. Return a two-element array [start, end] representing the range of indices where the target appears
2. If the target is not present, return [-1, -1]
3. The algorithm must achieve O(log n) time complexity
4. The input array is sorted in non-decreasing order (elements are in ascending order, with possible duplicates)

Constraints

• 0 ≤ nums.length ≤ 105
• -109 ≤ nums[i] ≤ 109
• nums is sorted in non-decreasing order
• -109 ≤ target ≤ 109

Examples

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3, 4] Explanation: The number 8 appears at indices 3 and 4.

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1, -1] Explanation: The number 6 does not appear in the array.

Example 3:

Input: nums = [], target = 0 Output: [-1, -1] Explanation: The array is empty, so the target cannot be found.

Example 4:

Input: nums = [1], target = 1 Output: [0, 0] Explanation: The single element matches the target at position 0.