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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解题思路：

又遇到O(logN)的时间复杂度要求，还是二分法。这里的重点是，我们利用二分法分两次来获得左右边界。那么如何保证能够获取到左或右的边界呢？以获取左边界为例：

start,end = 0, len(nums) - 1
while start < end:
    mid = (start + end) // 2
    if nums[mid] >= target:
        end = mid
    else:
        start = mid + 1

让最终停止时start = end，这样我们不用区分找到的边界到底在哪个指针上，要实现这一点，在更新start的时候，按照start = mid+1，end = mid更新是必要的，这两个是相互确定的。至于让start==end时，他们都能一起指到左指针，是由nums[mid] >= target要求，即使相等，还是右边end指针移动，并且地板除会让mid结果向左偏。

右边界也是一样的道理。

完整代码：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1,-1]
        start,end = 0, len(nums) - 1
        while start < end:
            mid = (start + end) // 2
            if nums[mid] >= target:
                end = mid
            else:
                start = mid + 1
                
        if nums[start] != target: # 没找到
            return [-1,-1]

        left,right = start, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] <= target:
                left = mid
            else:
                right = mid - 1
        return [start,right]