每日二题20201117（34. 在排序数组中查找元素的第一个和

34. 在排序数组中查找元素的第一个和最后一个位置

image-20201117145554994

思路

看到排序数组，基本上二分解法占一半，记得刚开始去字节面试的时候，面试官出了一题找出数组（先递增再递减）的峰值，也就是什么时候开始递减的。

答的是扫描，那样如果峰值很靠后的话，算法不是最优解，利用二分可以达到O(logN)，虽然最终在面试官的引导下一步一步写了出来，不过肯定有很多bug吧。

好像说了许多废话，说思路，首先找到那个匹配的数字，如果找不到，直接return [-1, -1]

如果找到了，2个while循环，一左一右开始找最小和最大索引。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        low, high = 0, len(nums)-1
        # start是标志位 确认是否找到target
        start = None
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] > target:
                high = mid - 1
            elif nums[mid] < target:
                low = mid + 1
            else:
                start = mid
                break
        if start is None:
            return [-1, -1]
        # 否则开始寻找两侧的节点
        left = right = start
        while left >= 0:
            # 如果左侧的不等于target了直接退出循环
            if left - 1 < 0 or nums[left-1] != target:
                break
            left -= 1

        while right < len(nums):
            if right + 1 >= len(nums) or nums[right+1] != target:
                break
            right += 1
        
        return left ,right

image-20201117151000953