1 题目描述

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

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

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

输入：nums = [], target = 0
输出：[-1,-1]

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

2 题解

这到题和剑指offer53-1比较像，如果我们从头进行遍历，那么没有利用到数组已排序的特点，对于有序的序列，大多数考察的都是二分法。

在这个题中，我们同样可以利用二分法去寻找刚大于target的那个元素的下标 rightIndex，则rightIndex-1 便是target的右界。

同样我们去寻找搞好小于target的元素的下标leftIndex, 则leftIndex+1便是target的左界，

然后判断左右界就可以直到答案了。

为了代码复用性，我们可以这样思考，由于数组是有序的，寻找左界不就相当于寻找刚好比它小的元素的刚好大于它的元素的下标，这样我们写一个函数就可以解决寻找左右界的问题。

代码如下：

def searchRange(self, nums: List[int], target: int) -> List[int]:

    def get_right_border(nums: List[int], tar: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] <= tar:
                left = mid + 1
            else:
                right = mid - 1
        return left

    if not List:
        return [-1, -1]
    left_border = get_right_border(nums, target - 1)
    right_border = get_right_border(nums, target)
    if left_border == right_border:
        return [-1, -1]
    return [left_border, right_border - 1]