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

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

解法一：二分

naive方法，先用二分找target，找到向两端扩张，看左右有没有相等的数。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        l = 0
        h = n-1
        res = []
        find = -1  #找到的数下标，初始为-1
        while l <= h:  #二分查找
            mid = (l+h) // 2
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                h = mid - 1
            else:  #若找到，用find记录位置，并跳出
                find = mid
                break
        if find == -1:  #若find仍为-1，说明没找到
            return [-1, -1]
        #向左右扩张
        left = right = find
        while left-1 >= 0 and nums[left-1] == nums[left]:
            left -= 1
        res.append(left)
        while right+1 < n and nums[right+1] == nums[right]:
            right += 1
        res.append(right)
        return res

解法二：二分找左右边界

修改二分查找的条件，可以分别找到连续个等于tar的数的最左端和最右端。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        leftRes,rightRes=0,0
        #找左边界
        left=0
        right = len(nums)-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid+1
            elif nums[mid] > target:
                right = mid-1
            elif nums[mid] == target:
                right = mid-1
        #超界或最终left位置不是target
        if left >= len(nums) or nums[left] != target:
            leftRes = -1
        else:
            leftRes = left

                #找右边界
        left=0
        right = len(nums)-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid+1
            elif nums[mid] > target:
                right = mid-1
            elif nums[mid] == target:
                left = mid+1    #只有这里与上面找左边界不同，其余代码相同
        #超界或最终right位置不是target
        if right < 0 or nums[right] != target:
            rightRes = -1
        else:
            rightRes = right

        return [leftRes, rightRes]