Given an array of integers nums
sorted in non-decreasing order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
. You must write an algorithm with O(log n)
runtime complexity.
For example:
nums = [5,7,7,8,8,10], target = 8
should return [3,4]
nums = [5,7,7,8,8,10], target = 6
should return [-1,-1]
nums = [], target = 0
should return [-1,-1]
Explain your approach, analyze the time and space complexity, and handle edge cases such as an empty array or when the target is not found.
A brute force solution would involve iterating through the array and checking each element to see if it matches the target. If a match is found, we record the index. We continue iterating to find the first and last occurrences.
def search_range_brute_force(nums, target):
first = -1
last = -1
for i in range(len(nums)):
if nums[i] == target:
if first == -1:
first = i
last = i
return [first, last]
O(n), where n is the number of elements in the array.
O(1), as we only use a constant amount of extra space.
Since the array is sorted, we can use binary search to find the first and last occurrences of the target value. This will give us a time complexity of O(log n).
nums[mid - 1] != target
or mid == 0
).nums[mid + 1] != target
or mid == len(nums) - 1
).def search_range(nums, target):
def find_first(nums, target):
left, right = 0, len(nums) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if nums[mid] == target:
index = mid
return index
def find_last(nums, target):
left, right = 0, len(nums) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
if nums[mid] == target:
index = mid
return index
first = find_first(nums, target)
last = find_last(nums, target)
return [first, last]
O(log n), because we perform two binary searches.
O(1), as we only use a constant amount of extra space.
[-1, -1]
. The code handles this case correctly.[-1, -1]
. The binary search returns -1 if the target is not found.