更多精彩内容，请关注【力扣中等题】。

题目

难度：★★★☆☆
类型：数组

给定一个按照升序排列的整数数组 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]

解答

方案1：线性遍历

使用临时变量flag记录在数组中是否出现过目标数字target，该参数默认为False，如果出现该数字，将flag设置为True，并且记录第一次出现的位置，且遍历过程实时更新最后一次出现的位置。

class Solution:
    def searchRange(self, nums, target):
        """
        :param nums: List[int]
        :param target: int
        :return: List[int]
        """
        first = last = -1
        flag = False
        for i in range(len(nums)):
            if nums[i] == target:
                if not flag:
                    first = last = i
                    flag = True
                else:
                    last = i
        return [first, last]

方案2：二分法

我们将问题拆分成两个子问题，即找到排序数组中目标数字出现的第一个位置和最后一个位置。这两个问题都可以用二分法方便求解，且编码过程对称。

class Solution:
    def searchRange(self, nums, target):
        """
        :param nums: List[int]
        :param target: int
        :return: List[int]
        """

        # 使用二分法找到target在nums中第一次出现的位置
        def find_left_index(nums, target):
            low, high = 0, len(nums) - 1
            while low < high:
                mid = low + (high - low) // 2
                if nums[mid] > target or target == nums[mid]:
                    high = mid
                else:
                    low = mid + 1
            return low if nums and nums[low] == target else -1

        # 使用二分法找到target在nums中最后一次出现的位置
        def find_right_index(nums, target):
            low, high = 0, len(nums) - 1
            while low < high:
                mid = low + (high - low) // 2 + 1
                if nums[mid] < target or target == nums[mid]:
                    low = mid
                else:
                    high = mid - 1
            return low if nums and nums[low] == target else -1

        return [find_left_index(nums, target), find_right_index(nums, target)]

如有疑问或建议，欢迎评论区留言~