Leetcode: Find first and last position of element in sorted arrays
Given a list of ascending sorted numbers, find the first and last occurrence of a target number. For example for the list [1,2,2,3,4] and target = 2, the result would be [1,2]. If the target number is not in the array, return [-1,-1].
We can solve this problem by using two binary searches. The first search finds the beginning and the second binary search finds the end of the target number. The default binary search algorithm is slightly modified. If the target element is found, the high position gets lowered to the current target mid - 1 position. Then the new comparison is made between half the new mid position which is between low and high.
For the second loop, this comparison is turned around and the low point is set to mid + 1 until the end of the chain is found.
from typing import List
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = [-1, -1]
low = 0
mid = 0
high = len(nums) - 1
while low <= high:
mid = (high + low) // 2 # Integer floor division
if nums[mid] == target:
high = mid - 1
res[0] = mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
low = 0
high = len(nums) - 1
mid = 0
while low <= high:
mid = (low + high) // 2 # Integer floor division
if nums[mid] == target:
low = mid + 1
res[1] = mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return res
if __name__ == '__main__':
s = Solution().searchRange
print(s([5,7,7,8,8,10], 8), [3,4])
print(s([5,6,7,7,8,8,10], 8), [4,5])
print(s([5,6,7,7,8,8,10,11], 8), [4,5])
print(s([5,7,7,8,8,10], 6), [-1,-1])
print(s([1,2,3,4], 1), [0,0])
print(s([1,2,2,3,4], 2), [1,2])
print(s([1,2,3,4], 0), [-1,-1])
print(s([], 1), [-1,-1])
Runtime: 185 ms, faster than 7.30% of Python3 online submissions for Find First and Last Position of Element in Sorted Array. Memory Usage: 15.5 MB, less than 48.10% of Python3 online submissions for Find First and Last Position of Element in Sorted Array.If the standard library of Python can be utilized, the whole solution becomes a lot simpler. Using
bisect allows us to perform binary search by passing the sorted array and the target. It is important to note that bisect_right returns one position to the right of the candidate and not the target itself. We can decrement the number by 1 to get the actual index. This is safe because we made sure that the number exists by first calling bisect_left. This method returns the position of the index if it’s in the array. There are two special cases that need to be handled.
- If all numbers are smaller, then the index is the
len(nums). In this case we immediately know that the number is not part of the array and can return[-1, -1]. - If the resulting number is
0, we need to check if the number at this position is equal to the number that we are looking for. If that is not the case, we can also immediately return[-1, -1].
from typing import List
import bisect
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
pos_l = bisect.bisect_left(nums, target)
if pos_l == len(nums) or nums[pos_l] != target:
return [-1, -1]
pos_r = bisect.bisect_right(nums, target)
return [pos_l, pos_r - 1]
if __name__ == '__main__':
s = Solution().searchRange
print(s([5,7,7,8,8,10], 8), [3,4])
print(s([5,7,7,8,8,10], 6), [-1,-1])
print(s([1,2,3,4], 1), [0,0])
print(s([1,2,2,3,4], 2), [1,2])
print(s([1,2,3,4], 0), [-1,-1])
print(s([], 1), [-1,-1])
Runtime: 156 ms, faster than 28.55% of Python3 online submissions for Find First and Last Position of Element in Sorted Array. Memory Usage: 15.5 MB, less than 9.48% of Python3 online submissions for Find First and Last Position of Element in Sorted Array.