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]

思路

1. 使用二分查找，先确定target是否在数组中；
2. 如果在数组中，则通过找到的位置向左和向右移动，找到起始和终点。

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