LC 34在排序数组中查找元素的第一个和最后一个位置Find First and Last Position of Element in Sorted Array　中等

在非递减数组中找出 target 出现的首末下标，不存在返回 [-1, -1]，要求 O(log n)。

思路 二分下界：lower_bound(target) 为首位置，lower_bound(target+1)-1 为末位置，需校验越界与元素相等。O(log n)。

class Solution:
    def searchRange(self, nums: List[int],
                    target: int) -> List[int]:
        def lower_bound(x: int) -> int:
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < x:
                    left = mid + 1
                else:
                    right = mid
            return left

        s = lower_bound(target)
        if s == len(nums) or nums[s] != target:
            return [-1, -1]
        return [s, lower_bound(target + 1) - 1]