问题描述
给定一个按照升序排列的整数数组 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]
解题思路
这个问题可以通过二分查找算法来解决，以达到题目要求的 O(log n) 时间复杂度。我们可以使用两次二分查找：一次查找目标值 target 的起始位置，另一次查找目标值的结束位置。
方法一：直接二分查找
这种方法在同一个二分查找过程中确定起始和结束位置，避免了重复查找和多余的判断。
代码实现
def searchRange(nums, target):
def binary_search(left, right, find_start):
index = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
index = mid
if find_start:
right = mid - 1
else:
left = mid + 1
return index
start = binary_search(0, len(nums) - 1, True)
if start == -1:
return [-1, -1] # Early exit if `target` is not found
end = binary_search(0, len(nums) - 1, False)
return [start, end]
# 示例
print(searchRange([5,7,7,8,8,10], 8)) # 输出: [3, 4]
print(searchRange([5,7,7,8,8,10], 6)) # 输出: [-1, -1]
算法图解
以下是一个针对数组 [5,7,7,8,8,10] 查找 8 的具体流程的 ASCII 图解：
数组: [5, 7, 7, 8, 8, 10]
目标值: 8
二分查找过程的 ASCII 图解
初始数组设置:
索引: 0 1 2 3 4 5
值: [5, 7, 7, 8, 8, 10]
初始指针:
左指针 (L) -> 0 右指针 (R) -> 5
步骤 1: 计算中间点:
中间点 (M) -> (0+5)/2 = 2
L M R
| | |
[5, 7, 7, 8, 8, 10]
中值 < 目标值, 左指针移动到中点右侧
步骤 2: 移动左指针:
左指针 (L) -> 3
L R
| |
[5, 7, 7, 8, 8, 10]
新中点 (M) -> (3+5)/2 = 4
步骤 3: 计算新中点:
中间点 (M) -> 4
L M R
| | |
[5, 7, 7, 8, 8, 10]
中值 == 目标值, 展开查找完整范围
步骤 4: 扩展查找开始和结束位置:
从位置3开始, 向左检查 nums[3-1] 是否为8, 向左递减找到开始
开始位置 -> 3
从位置4开始, 向右检查 nums[4+1] 是否为8, 向右递增找到结束
结束位置 -> 4
最终结果: [3, 4]
ASCII 图解说明
-
初始设置：初始时，
左指针位于数组起始位置（0），右指针位于数组末端（5）。 -
首次计算中间点：通过表达式
(左指针 + 右指针) / 2计算中间点。中间点（2）的值为7，小于目标值8，所以将左指针移动到中点的右侧。 -
移动左指针：左指针更新至索引3，重新计算中间点。
-
计算新中间点：新的中间点位置是4，数值与目标值相等，现在需要确定该目标值的完整范围。
-
扩展查找范围：
- 查找开始位置：从索引3开始向左扩展，直到数组元素不等于8。
- 查找结束位置：从索引4开始向右扩展，直到数组元素不等于8。
这种方法不仅利用了二分查找的高效性在对数时间内找到结果，还通过额外的线性扫描处理来定位目标值的完整范围，适合解决需要快速解答范围查询的问题。
方法二：优化的二分查找
分别进行两次二分查找：第一次找到第一个不小于 target 的位置（可能的开始位置），第二次找到第一个大于 target 的位置减一（可能的结束位置）。
代码实现
def searchRange(nums, target):
def findFirstPosition():
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
def findLastPosition():
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
start = findFirstPosition()
end = findLastPosition()
# Check if `target` is out of bounds
if start <= end and 0 <= start < len(nums) and nums[start] == target and nums[end] == target:
return [start, end]
return [-1, -1]
# 示例
print(searchRange([5,7,7,8,8,10], 8)) # 输出: [3, 4]
print(searchRange([5,7,7,8,8,10], 6)) # 输出: [-1, -1]
算法分析
通过表格来展示这两种方法的时间复杂度、空间复杂度以及它们的主要优势和劣势。
| 特征 | 方法一：直接二分查找 | 方法二：优化的二分查找 |
|---|---|---|
| 时间复杂度 | O(log n) | O(log n) |
| 空间复杂度 | O(1) | O(1) |
| 优势 | - 简化逻辑，只需一个二分查找函数，通过传入参数控制查找开始或结束。 - 直观易懂，适用于对二分查找流程有清晰理解的情况。 | - 代码结构清晰，将寻找开始位置和结束位置的任务分开处理，易于维护。 - 更符合一般二分查找的模式，逻辑分明，减少了错误和调试时间。 |
| 劣势 | - 逻辑在单个函数中可能稍显复杂，尤其是在处理边界条件时。 - 如果未来需要修改或扩展查找逻辑，可能需要重写较多代码。 | - 实现两个函数，代码行数较多。 - 如果问题场景不需要严格分离起始和结束位置查找，可能会导致轻微的效率下降。 |
总结
两种方法都利用二分查找来定位目标值的起始和结束位置，但第二种方法通过分离查找起始位置和结束位置的逻辑，使得代码更为清晰和易于管理。每种方法都符合题目的时间复杂度要求，具体使用哪种取决于个人偏好
