Space
Open
From Fieldwork
Scales
Archive
Non-decreasing is actually code for "sorted, but there might be duplicates."
class Solution:
def searchRange(self, nums, target):
def find_first(nums, target):
low, high = 0, len(nums) - 1
first_idx = -1
while low <= high:
mid = (low + high) // 2
if nums[mid] >= target:
if nums[mid] == target:
first_idx = mid
high = mid - 1
else:
low = mid + 1
return first_idx
def find_last(nums, target):
low, high = 0, len(nums) - 1
last_idx = -1
while low <= high:
mid = (low + high) // 2
if nums[mid] <= target:
if nums[mid] == target:
last_idx = mid
low = mid + 1
else:
high = mid - 1
return last_idx
return [find_first(nums, target), find_last(nums, target)]bisect_left gives you the first index where the target could be placed while maintaining order.
bisect_right gives you the last index + 1.
The only catch is that bisect doesn't check if the target actually exists in the list; it just tells us where it would go. We'd have to add a manual check.
Edge Cases: If the list is empty or the target isn't present, the manual search naturally returns -1. In the bisect version, we must verify the index is within range(len(nums)).
class Solution:
def searchRange(self, nums, target):
left = bisect.bisect_left(nums, target)
right = bisect.bisect_right(nums, target) - 1
# Check if left is within bounds and actually points to the target
if left < len(nums) and nums[left] == target:
return [left, right]
return [-1, -1]Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode