Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
思路
- 使用二分查找，先确定target是否在数组中；
- 如果在数组中，则通过找到的位置向左和向右移动，找到起始和终点。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
result = [-1, -1]
found = False
left = 0
right = len(nums) - 1
while left <= right and left < len(nums) and right >= 0 :
mid = (left + right) // 2
if nums[mid] < target :
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
found = True
break
if found is True:
left = mid
right = mid
while left >= 0 and nums[left] == target:
left -= 1
while right < len(nums) and nums[right] == target:
right += 1
result = [left + 1, right - 1]
return result
