响应式网站 解决方案,c 做注册网站,推广普通话的顺口溜,alexa全球网站排名本文目录 1 中文题目2 求解方法#xff1a;左右边界二分查找2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
给定一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存… 本文目录 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]≤109nums 是一个非递减数组 − 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 题目总结
题目难度中等 数据结构数组 应用算法左右边界二次二分查找
