34 - Find First And Last Position Of Element In Sorted Array
Written on July 25, 2022
Tweet
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.
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
left = right = mid
while left >= 0 and nums[left] == target:
left -= 1
while right < len(nums) and nums[right] == target:
right += 1
return [left + 1, right - 1]
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return [-1, -1]