34. Search for a Range

在一个有序的数组中找到找到目标数字的起始坐标和结束坐标，如果不存在则返回[-1, -1]

思路：二分查找，注意边界条件，找到目标数字的下标，然后分别往左右扩展，找到左右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 5 star
        low, high = 0, len(nums) - 1
        while low <= high:
            middle = (low+high)//2
            if target > nums[middle]:
                low = middle + 1
            elif target < nums[middle]:
                high = middle - 1
            else:
                start = end = middle
                while start > 0 and nums[start-1] == target:
                    start -= 1
                while end+1 < len(nums) and nums[end+1] == target:
                    end += 1
                return [start, end]
        return [-1, -1]