leetcode34题 在排序数组中查找元素的第一个和最后一个位置

目录34. 在排序数组中查找元素的第一个和最后一个位置题目描述思路核心思想关键点代码解法一:闭区间[l, r]解法二:左闭右开[l, r)解法三:开区间(l, r)答疑Q: 闭区间写法中,nums[mid] target时为什么是r mid - 1?mid不可能是答案吗?不会错过正确答案吗?复杂度分析题号: “34”难度: 中等标签: 二分查找,数组链接: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/34. 在排序数组中查找元素的第一个和最后一个位置题目描述给定一个升序排列的整数数组nums和一个目标值target,找出target在数组中的第一个和最后一个位置;若数组中不存在target,返回[-1, -1]。输入:nums(升序数组,可能含重复元素)、target输出:[start, end](下标),不存在时返回[-1, -1]进阶: 要求时间复杂度为 O(log n)思路核心思想两次二分,分别定位左边界与右边界:左边界lowerBound(nums, target):第一个 target的下标右边界lowerBound(nums, target 1) - 1:即「第一个 target的位置」再往前一位,得到最后一个 target的下标若start n或nums[start] ! target,说明目标不存在,返回[-1, -1];否则返回[start, end](起点存在时,终点必然存在)。关键点完整的需求转化表见 [[二分查找模板]],本题只需用到其中两行:需求写法不存在时第一个 x的下标lowerBound(nums, x)n最后一个 x的下标lowerBound(nums, x 1) - 1-1两次二分相互独立,各 O(log n),总复杂度 O(log n)。代码三种区间写法的lowerBound行为完全一致,searchRange主逻辑共用。默认推荐左闭右开(与 C STLlower_bound语义一致)。解法一:闭区间[l, r]classSolution{public:intlowerBound(vectorintnums,inttarget){intl0,rnums.size()-1;while(lr){intmidl(r-l)/2;// 防止溢出if(nums[mid]target)rmid-1;// 答案至多为 mid,收缩右边界elselmid1;}returnl;// 或 r 1}vectorintsearchRange(vectorintnums,inttarget){intstartlowerBound(nums,target);if(startnums.size()||nums[start]!target)return{-1,-1};// 起点不存在,终点必然不存在intendlowerBound(nums,target1)-1;return{start,end};}};解法二:左闭右开[l, r)classSolution{public:intlowerBound(vectorintnums,inttarget){intl0,rnums.size();// 区间 [0, n),r 取 n 可表示越界while(lr){intmidl(r-l)/2;if(nums[mid]target)rmid;// 答案在 [l, mid] 内,保留 midelselmid1;}returnl;// 或 r}vectorintsearchRange(vectorintnums,inttarget){intstartlowerBound(nums,target);if(startnums.size()||nums[start]!target)return{-1,-1};intendlowerBound(nums,target1)-1;return{start,end};}};解法三:开区间(l, r)classSolution{public:intlowerBound(vectorintnums,inttarget){intl-1,rnums.size();// 区间 (-1, n),哨兵可表示边界while(l1r){intmidl(r-l)/2;// 循环保证 r - l 2,mid 必在区间内if(nums[mid]target)rmid;elselmid;}returnr;// 或 l 1}vectorintsearchRange(vectorintnums,inttarget){intstartlowerBound(nums,target);if(startnums.size()||nums[start]!target)return{-1,-1};intendlowerBound(nums,target1)-1;return{start,end};}};答疑Q: 闭区间写法中,nums[mid] target时为什么是r mid - 1?mid不可能是答案吗?不会错过正确答案吗?关键在于区分二分范围与答案所在范围。lowerBound维护的循环不变量是:答案(第一个 target的位置)始终落在[l, r 1]中。当nums[mid] target时,mid已经满足条件,而答案必须是「第一个」满足条件的位置,所以答案至多为mid——mid右侧全部排除,二分范围收缩为[l, mid - 1],而可能答案mid由边界r 1携带,不会被丢弃。同理,若target大于区间内所有元素,循环结束时l r 1,答案正是l。二分收缩的是候选区间,答案由边界l/r携带,永不丢失。其余两种写法同理:左闭右开由r携带,开区间由r(或l 1)携带。复杂度分析时间复杂度空间复杂度说明O(log n)O(1)两次二分各 O(log n);原地操作,无额外空间