Find First and Last Position of Element in Sorted Array

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Input: nums = [], target = 0
Output: [-1,-1]
class Solution(object):
def searchRange(self, nums, target):
“””
:type nums: List[int]
:type target: int
:rtype: List[int]
“””
if not nums: return [-1, -1]

def lowerBound(nums, target):
i, j = 0, len(nums)
while i<j:
mid = (i+j)/2
if nums[mid] >= target:
j = mid
else:
i = mid + 1
return i

def higherBound(nums, target):
i, j = 0, len(nums)
while i<j:
mid = (i+j)/2
if nums[mid] > target:
j = mid
else:
i = mid + 1
return i

lower = lowerBound(nums, target)
higher = higherBound(nums, target)-1
if lower == len(nums) or nums[lower]!=target:
return [-1, -1]

return [lower, higher]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store