襄阳企业网站建设电脑零基础培训班
本文目录
- 1 中文题目
- 2 求解方法：左右边界二分查找
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
- 3 题目总结
1 中文题目
给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 ≤ n u m s . l e n g t h ≤ 1 0 5 0 \leq nums.length \leq10^5 0≤nums.length≤105
- − 1 0 9 ≤ n u m s [ i ] ≤ 1 0 9 -10^9 \leq nums[i] \leq 10^9 −109≤nums[i]≤109
nums是一个非递减数组- − 1 0 9 ≤ t a r g e t ≤ 1 0 9 -10^9 \leq target \leq 10^9 −109≤target≤109
2 求解方法：左右边界二分查找
2.1 方法思路
方法核心
- 使用两次改进的二分查找
- 分别查找目标值的左右边界
- 通过不同的条件控制边界的移动
实现步骤
（1）查找左边界的过程：
- 初始化左右指针，分别指向数组的开始和结束
- 在循环中计算中间位置
- 当找到大于或等于目标值的元素时，记录该位置并继续往左找
- 当找到小于目标值的元素时，需要往右找
- 最终找到第一个等于目标值的位置
- 需要判断是否越界以及是否真的找到了目标值
（2）查找右边界的过程：
- 同样初始化左右指针
- 在循环中不断更新中间位置
- 当找到小于或等于目标值的元素时，继续往右找
- 当找到大于目标值的元素时，需要往左找
- 最终找到最后一个等于目标值的位置
- 同样需要进行边界检查
方法示例
输入：nums = [5,7,7,8,8,10], target = 8左边界查找过程：
1. 初始状态：left = 0, right = 5mid = 2, nums[mid] = 7 < targetleft = mid + 1 = 32. 第二次迭代：left = 3, right = 5mid = 4, nums[mid] = 8 == targetright = mid - 1 = 33. 第三次迭代：left = 3, right = 3mid = 3, nums[mid] = 8 == targetright = mid - 1 = 24. 循环结束：left = 3，找到左边界右边界查找过程：
1. 初始状态：left = 0, right = 5mid = 2, nums[mid] = 7 < targetleft = mid + 1 = 32. 第二次迭代：left = 3, right = 5mid = 4, nums[mid] = 8 == targetleft = mid + 1 = 53. 第三次迭代：left = 5, right = 5mid = 5, nums[mid] = 10 > targetright = mid - 1 = 44. 循环结束：right = 4，找到右边界返回：[3, 4]
2.2 Python代码
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binary_search_left(nums, target):# 寻找左边界的二分查找left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 如果中间值大于或等于目标值，继续往左找if nums[mid] >= target:right = mid - 1# 如果中间值小于目标值，往右找else:left = mid + 1# 判断是否找到目标值if left >= len(nums) or nums[left] != target:return -1return leftdef binary_search_right(nums, target):# 寻找右边界的二分查找left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 如果中间值小于或等于目标值，继续往右找if nums[mid] <= target:left = mid + 1# 如果中间值大于目标值，往左找else:right = mid - 1# 判断是否找到目标值if right < 0 or nums[right] != target:return -1return right# 特殊情况处理if not nums:return [-1, -1]# 分别查找左右边界left_bound = binary_search_left(nums, target)right_bound = binary_search_right(nums, target)return [left_bound, right_bound]
2.3 复杂度分析
- 时间复杂度：O(log n)
- 两次二分查找
- 每次二分查找的时间复杂度为O(log n)
- 空间复杂度：O(1)
- 只使用常数额外空间
- 不随输入规模增长
3 题目总结
题目难度：中等
数据结构：数组
应用算法：左右边界二次二分查找