Search the left most element and right most element separately.
Push the "right' pointer to left as far as possible to find the left most element.
Push the "left" pointer to right as far as possible to find the right most element.
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
def leftMost(left, right):
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid # push 'right' to left as far as possible
if right < len(nums) and nums[right] == target:
return right
return -1
def rightMost(left, right):
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1 # push 'left' to right as far as possible
else:
right = mid
return left - 1
left = leftMost(0, len(nums))
if left == -1:
return [-1, -1]
return [left, rightMost(left, len(nums))]
Use built-in function:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return -1, -1
right = bisect.bisect_right(nums, target) - 1
return left, right
Edited on 02/27/2021. Use buillt-in lib.
No comments:
Post a Comment