34. Find First and Last Position of Element in Sorted Array
[Medium] “Given an array of integers sorted in ascending order, find the starting and ending position of a target value, in O(log n) (otherwise return [-1, -1])."
Note: absoutely hated this one, still hard to understand even looking a the solution, maybe too tired for it.
Python3:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = self.search_index(nums, target, True)
if left == len(nums) or nums[left] != target:
return [-1, -1]
else:
right = self.search_index(nums, target, False) - 1
return [left, right]
def search_index(self, nums: List[int], target: int, low: bool) -> int:
left = 0
right = len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] > target or (low and target == nums[mid]):
right = mid
else:
left = mid + 1
return left