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.
Solution
Binar search
Code
- submit code
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
result = []
result.append(self.left_bound(nums,target))
result.append(self.right_bound(nums,target))
return result
def left_bound(self,nums,target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
right = mid - 1
if left >= len(nums) or nums[left] != target:
return -1
return left
def right_bound(self,nums,target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
left = mid +1
if right < 0 or nums[right] != target:
return -1
return right
- full code
class Solution:
def searchRange(self, nums, target):
result = []
result.append(self.left_bound(nums,target))
result.append(self.right_bound(nums,target))
return result
def left_bound(self,nums,target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
right = mid - 1
if left >= len(nums) or nums[left] != target:
return -1
return left
def right_bound(self,nums,target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
left = mid +1
if right < 0 or nums[right] != target:
return -1
return right
nums = [5, 7, 7, 8, 8, 10]
target = 8
S = Solution()
print(S.searchRange(nums,target))