欢迎关注 leetcode 专栏

• 题目
• 解法
  • 常规解法
  • 递归解法
  • Python 专属解法

题目

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

链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

解法

常规解法

思路：把一个问题拆分成两个子问题：找左边界 + 找右边界，解法都是一样的，只是循环终止条件略有差异。

对于左边界，满足以下条件时认为找到了：

1. 值与 target 相同
2. 左边没有其他值（即索引为0）或者左边的值比 target 小

对于右边界，满足以下条件时认为找到了：

1. 值与 target 相同
2. 右边没有其他值（即索引为总长度 - 1）或者右边的值比 target 大

# 常规解法
class Solution:
    def searchRange(self, nums: int, target: int) -> int:
        if not nums: return [-1, 1]
        return [self.find_left_range(nums, target), self.find_right_range(nums, target)]

    def find_left_range(self, nums, target):        
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = left + (right - left) // 2
            if nums[middle] < target:
                left = middle + 1
            else:
                if nums[middle] == target and (middle == 0 or nums[middle - 1] < target):
                    return middle
                right = middle - 1
        return -1  

    def find_right_range(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = left + (right - left) // 2
            if nums[middle] > target:
                right = middle - 1
            else:
                if nums[middle] == target and (middle == len(nums) - 1 or nums[middle + 1] > target):
                    return middle
                left = middle + 1
        return -1 

空间复杂度 O(1)，只是额外申请了几个变量的空间。
时间复杂度 O(logn)，就是二分查找的复杂度。

可以看出，查找左右边界的过程是分离的，所以也有优化的空间，也就是复用一部分结果。比如先用二分查找法，在找到任意一个目标值时，对于此时的 left、middle、right ，分别使用 [left, middle] 作为查找左边界的初始值，使用 [middle, right] 作为查找右边界的初始值。不过，这种操作的复杂度没变，时间和空间上并没有可见的改善。

递归解法

递归解法与常规解法相比而言，有一个容易犯错的地方，就是当 nums[middle] == target 时，下一个递归的初始值要如何选择。

1. 当查找左边界时，如果 nums[middle] == target ，那么 middle 只能是新的临时右边界初始值；
2. 当查找右边界时，如果 nums[middle] == target ，那么 middle 只能是新的临时左边界初始值；

# 递归解法
class Solution:
    def searchRange(self, nums: int, target: int) -> int:
        if not nums: return [-1, -1]
        return [self.find_left_range(nums, target, 0, len(nums) - 1), 
                self.find_right_range(nums, target, 0, len(nums) - 1)]

    def find_left_range(self, nums, target, left, right):
        if left > right: return -1
        middle = left + (right - left) // 2
        if nums[middle] == target and (middle == 0 or nums[middle - 1] < target):
            return middle
        elif nums[middle] < target:
            return self.find_left_range(nums, target, middle + 1, right)
        else:
            return self.find_left_range(nums, target, left, middle - 1)

    def find_right_range(self, nums, target, left, right):
        if left > right: return -1
        middle = left + (right - left) // 2
        if nums[middle] == target and (middle == len(nums) - 1 or nums[middle + 1] > target):
            return middle
        elif nums[middle] <= target:
            return self.find_right_range(nums, target, middle + 1, right)
        else:
            return self.find_right_range(nums, target, left, middle - 1)

空间复杂度 O(logn)，最差情况下递归的深度就是logn。
时间复杂度 O(logn)，不变。

Python专属解法

python 的内置库 bisect ，可以让我们很方便地对有序列表进行操作。

这里主要使用两个函数：

1. bisect_left(nums, x)：对于 x，找到在有序数组 nums 的合适插入位置（如果数组里有多个 x 则返回最左侧的插入位置，即第一个 x 的索引），以保持有序。
2. bisect_right(nums, x)：对于 x，找到有序数组 nums 的合适插入位置（如果数组里有多个 x 则返回最右侧的插入位置，即最后一个 x 的索引 + 1），以保持有序。

import bisect

class Solution:
    def searchRange(self, nums: int, target: int) -> int:
        if not nums: return [-1, -1]

        left = bisect.bisect_left(nums, target)
        right = bisect.bisect_right(nums, target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        else:
            return [left, right - 1]

还没看过 bisect 库的源码，但一般 python 内置库为了满足各种场景的需要，会额外加入一些异常处理逻辑，因此处理时间也会更长一些。

更多刷题，尽在 leetcode 专栏