34. Find First and Last Position

【Description】
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]

【Idea】

O(log n) 时间复杂度，就要考虑分治

先找到匹配的一个下标，然后向左向右遍历找她的重复值

【Solution】

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if nums == [] or nums[0] > target or nums[-1] < target:
            return [-1, -1]
        l = 0
        r = len(nums) -1
        while l <= r:
            index = (l+r)//2
            if nums[index] == target:
                i, j = index, index
                while i - 1 >= 0 and nums[i - 1] == target:
                    i -= 1
                while j + 1 < len(nums) and nums[j + 1] == target:
                    j += 1
                return [i, j]
            elif nums[index] > target:
                r = index -1
            else:
                l = index + 1
        if nums[index] != target:
            return [-1, -1]