欢迎关注 leetcode 专栏
题目
给定一个按照升序排列的整数数组 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
解法
常规解法
思路：把一个问题拆分成两个子问题：找左边界 + 找右边界，解法都是一样的，只是循环终止条件略有差异。
对于左边界，满足以下条件时认为找到了：
- 值与 target 相同
- 左边没有其他值（即索引为0）或者左边的值比 target 小
对于右边界，满足以下条件时认为找到了：
- 值与 target 相同
- 右边没有其他值（即索引为总长度 - 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 时，下一个递归的初始值要如何选择。
- 当查找左边界时，如果 nums[middle] == target ，那么 middle 只能是新的临时右边界初始值；
- 当查找右边界时，如果 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 ，可以让我们很方便地对有序列表进行操作。
这里主要使用两个函数：
- bisect_left(nums, x)：对于 x，找到在有序数组 nums 的合适插入位置（如果数组里有多个 x 则返回最左侧的插入位置，即第一个 x 的索引），以保持有序。
- 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 专栏
