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

见注释。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        """
        32ms ** 97.23% ///// 14.6MB ** 5.07%
        换一种写法，重新组织代码，按照youtube上大神的模式来写 https://www.youtube.com/watch?v=bU-q1OJ0KWw
        1.整体上简洁清晰 2. 省去了边界处理的麻烦
        """
        left = self.findLeft(nums, target)
        right = self.findRight(nums, target)
        return [left, right]
    
    def findLeft(self, nums, target):
        left = -1       # 初始化
        start = 0
        end = len(nums) - 1
        while start <= end:
            middle = start + (end - start) // 2
            if nums[middle] >= target:                  #　这里的　>= 是很关键而且巧妙的一步，让它自身来突破边界
                end = middle - 1
            else:
                start = middle + 1
            if nums[middle] == target:
                left = middle
        return left 

    def findRight(self, nums, target):
        right = -1       # 初始化
        start = 0
        end = len(nums) - 1
        while start <= end:
            middle = start + (end - start) // 2
            if nums[middle] <= target:                  #　这里的　>= 是很关键而且巧妙的一步，让它自身来突破边界
                start = middle + 1
            else:
                end = middle - 1
            if nums[middle] == target:
                right = middle
        return right
 

        """
        44ms ** 78.04% ///// 14.4 ** 5.07%
        """
        # 二分查找  
        # 先尝试按照自己的老套路来写。然后按照youtube上大神的模式来写。分成几个小的方法来拼凑一起。
        # start = 0 
        # end = len(nums)-1 
        # found = False
        # while start <= end:
        #     middle = start + (end -start) // 2
        #     if nums[middle] == target:
        #         found = True
        #         break 
        #     elif nums[middle] > target:
        #         end = middle - 1 
        #     else:
        #         start = middle + 1

        # if not found:
        #     return [-1, -1]
        # else:
        #     # 说明找到了。此时可以获取 middle 的值，然后再往2侧扩展 
        #     # print(middle, nums[middle])
        #     left = middle
        #     right = middle 
        #     while left >-1 and nums[left] == target:
        #         left -= 1
        #     while right < len(nums) and nums[right] == target:
        #         right += 1 
        #     return [left+1, right-1]    # 这里也还是需要再还原一下的，因为上面的while里面又多操作了一下。