LC34. Find First and Last Position of Element in Sorted Array
Link to problem: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
This is a simple application of binary search. The hard is part is how to tweak binary search to return the first (or last) index of a given target.
We do binary search as normal, and compare nums[mid]
and target
. If they are equal, we can’t just return mid
, because this might be any of the target
s in the array; we also can’t let high = mid
or low = mid
and keep searching, because it is possible that low
and high
will never meet in this case. Therefore, we must manually check if nums[mid]
is the first (or last) target
in the array. If so, just return mid
; otherwise, let high = mid - 1
or low = mid + 1
and keep searching.
这是一道二分查找的简单应用题,难点在于查找某个元素的第一个和最后一个下标。
我们正常进行二分查找,比较 nums[mid]
与 target
。如果它们相等,我们不能直接返回,因为返回的可能是任意一个 target
。那我们可以直接令 high = mid
或者 low = mid
继续查找吗?也不可以,因为这样会造成 low
和 high
永远无法相遇。所以必须在此时检查 nums[mid]
是否是第一个(最后一个)target
。如果是的话直接返回 mid
,否则才令 high = mid - 1
或者 low = mid + 1
继续查找。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums, target, low, high, first):
while low < high:
# print(low, high)
mid = (low + high) // 2
if first:
if nums[mid] == target and \
(mid == 0 or nums[mid-1] < target):
return mid
elif nums[mid] >= target:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] == target and \
(mid == len(nums)-1 or nums[mid+1] > target):
return mid
elif nums[mid] <= target:
low = mid + 1
else:
high = mid - 1
if low == high and nums[low] == target:
return low
else:
return -1
l = binarySearch(nums, target, 0, len(nums)-1, True)
r = binarySearch(nums, target, 0, len(nums)-1, False)
return [l, r]