34.
Find First and Last Position of Element in Sorted Array
Medium
Problem Description
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Examples
Input: [5,7,7,8,8,10], 8
Output: [3,4]
Input: [5,7,7,8,8,10], 6
Output: [-1,-1]
Input: [], 0
Output: [-1,-1]
Constraints
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is a non-decreasing array.
-10^9 <= target <= 10^9
Approach to Solve
Use a two-pointer approach to find the target.
Code Implementation
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums, target, leftmost):
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
result = mid
if leftmost:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
left = binarySearch(nums, target, True)
if left == -1:
return [-1, -1]
right = binarySearch(nums, target, False)
return [left, right]Explanation
This solution uses a two-pointer approach to find the target. Here's a detailed explanation of the algorithm:
- Initialize left and right pointers to the start and end of the array, respectively.
- While left is less than or equal to right:
- Calculate the middle index mid.
- If nums[mid] is equal to the target, return [self.findLeft(nums, target, mid), self.findRight(nums, target, mid)].
- If nums[mid] is less than the target, move the left pointer to mid + 1.
- Otherwise, move the right pointer to mid - 1.
- If the target is not found, return [-1, -1].
Complexity
- Time Complexity: O(log n)
- Space Complexity: O(1)
Code copied to clipboard!