34. 在排序數(shù)組中查找元素的第一個和最后一個位置

image-20201117145554994

思路

看到排序數(shù)組，基本上二分解法占一半，記得剛開始去字節(jié)面試的時候，面試官出了一題找出數(shù)組（先遞增再遞減）的峰值，也就是什么時候開始遞減的。

答的是掃描，那樣如果峰值很靠后的話，算法不是最優(yōu)解，利用二分可以達到O(logN)，雖然最終在面試官的引導(dǎo)下一步一步寫了出來，不過肯定有很多bug吧。

好像說了許多廢話，說思路，首先找到那個匹配的數(shù)字，如果找不到，直接return [-1, -1]

如果找到了，2個while循環(huán)，一左一右開始找最小和最大索引。

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]
        # 否則開始尋找兩側(cè)的節(jié)點
        left = right = start
        while left >= 0:
            # 如果左側(cè)的不等于target了直接退出循環(huán)
            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