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

Leetcode Link: 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

题目

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

解法一

思路：根据提示，可知本题必然使用二分法。

但是本题不能使用二分查到一个target后再通过 +1 或者 -1 的遍历去查找上下边界，因为这样的结果是一个$O(N)$的复杂度。本题必需使用两次二分查找分别找到上下边界。

本题使用红蓝边界的二分建模方法，该建模方法需要重点考虑边界的划分条件。

题解：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = -1
        right = len(nums)
        res = [-1,-1]
        # 找下边界，红蓝边界的条件是：蓝色<target，最后检查right
        while(left+1 != right): # 边界不重合就继续
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        if (right<len(nums) and nums[right]>target) or right>=len(nums):
            return [-1, -1]
        elif right<len(nums) and nums[right]==target:
            res[0] = right
        
        # 找上边界，红蓝边界的条件是：蓝色<=target，最后检查left
        left = -1
        right = len(nums)
        while(left+1!=right):
            mid = (left+right) // 2
            if nums[mid] <= target:
                left = mid
            else:
                right = mid
        res[1] = left
        return res