电商网站设计与制作,城阳网站建设公司,买卖网站建设,qt科技感ui界面34. 在排序数组中查找元素的第一个和最后一个位置
一、算法逻辑#xff08;逐步通顺讲解每一步思路#xff09;
该算法用于在一个升序排列的数组 nums 中查找某个目标值 target 的第一个出现的位置和最后一个出现的位置。
✅ 1️⃣ 定义 lower_bound 函数
def lower_boun…34. 在排序数组中查找元素的第一个和最后一个位置
一、算法逻辑逐步通顺讲解每一步思路
该算法用于在一个升序排列的数组 nums 中查找某个目标值 target 的第一个出现的位置和最后一个出现的位置。
✅ 1️⃣ 定义 lower_bound 函数
def lower_bound(self, nums: List[int], target: int) - int:left, right -1, len(nums)while left 1 right:mid (left right) // 2if nums[mid] target:right midelse:left midreturn right
这个函数返回的是第一个大于等于 target 的索引位置。使用的是左闭右开区间 [left1, right) 的二分写法可以避免边界处理错误。循环终止时right 就是第一个满足 nums[right] target 的位置。
✅ 2️⃣ 查找目标值的起始位置
start self.lower_bound(nums, target)
如果 nums[start] ! target 或者 start len(nums)说明数组中不存在该元素直接返回 [-1, -1]。
✅ 3️⃣ 查找目标值的结束位置
end self.lower_bound(nums, target 1) - 1
我们通过查找 target 1 的第一个位置再减 1就得到了 target 的最后一个位置。因为数组是有序的所以 target 1 第一次出现之前的所有元素都是 target。
✅ 4️⃣ 返回结果
return [start, end] 二、核心点总结
✅ 利用两次二分查找精准定位范围
使用两次「lower_bound」分别找到起始位置和结束位置避免了线性扫描效率高。
✅ 巧妙的“target 1”技巧
不需要额外编写一个 upper_bound 函数只需将目标值加一即可复用 lower_bound 找出右边界。
✅ 适合面试高频题型
本题是典型的二分查找变形题考察对边界条件的理解和对二分思想的灵活运用。
✅ 可扩展性强
此种思路也可推广到其他变种问题如统计某数字在排序数组中出现的次数剑指 Offer 题等。
class Solution:def lower_bound(self, nums:List[int], target:int)- int:left, right -1, len(nums)while left1 right:mid (leftright)//2if nums[mid]target:right midelse:left midreturn rightdef searchRange(self, nums: List[int], target: int) - List[int]:start self.lower_bound(nums, target)if startlen(nums) or nums[start] ! target:return [-1,-1]end self.lower_bound(nums, target1)-1return [start, end] 三、时间复杂度分析
✅ 每次调用 lower_bound 是一个标准的二分查找过程
时间复杂度为 O(log n)
✅ 整体算法执行了两次二分查找
总体时间复杂度为 O(log n) 四、空间复杂度分析
✅ 整个过程中没有使用任何额外的数据结构
所有变量都是常数级的局部变量
✅ 空间复杂度为 O(1) ✅ 总结一句话
这段算法通过两次二分查找定位目标值的起始与结束位置巧妙利用 target 1 技巧避免重复编写 upper_bound具有高效、简洁、稳定的特点是解决有序数组中查找范围类问题的经典解法之一非常适合作为面试准备的重点内容。
