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](起点存在时,终点必然存在)。

关键点

完整的需求转化表见 [[二分查找模板]],本题只需用到其中两行:

两次二分相互独立,各 O(log n),总复杂度 O(log n)。

代码

三种区间写法的lowerBound行为完全一致,searchRange主逻辑共用。默认推荐左闭右开(与 C++ STLlower_bound语义一致)。

解法一:闭区间[l, r]

classSolution{public:intlowerBound(vector<int>&nums,inttarget){intl=0,r=nums.size()-1;while(l<=r){intmid=l+(r-l)/2;// 防止溢出if(nums[mid]>=target)r=mid-1;// 答案至多为 mid,收缩右边界elsel=mid+1;}returnl;// 或 r + 1}vector<int>searchRange(vector<int>&nums,inttarget){intstart=lowerBound(nums,target);if(start==nums.size()||nums[start]!=target)return{-1,-1};// 起点不存在,终点必然不存在intend=lowerBound(nums,target+1)-1;return{start,end};}};

解法二:左闭右开[l, r)

classSolution{public:intlowerBound(vector<int>&nums,inttarget){intl=0,r=nums.size();// 区间 [0, n),r 取 n 可表示越界while(l<r){intmid=l+(r-l)/2;if(nums[mid]>=target)r=mid;// 答案在 [l, mid] 内,保留 midelsel=mid+1;}returnl;// 或 r}vector<int>searchRange(vector<int>&nums,inttarget){intstart=lowerBound(nums,target);if(start==nums.size()||nums[start]!=target)return{-1,-1};intend=lowerBound(nums,target+1)-1;return{start,end};}};

解法三:开区间(l, r)

classSolution{public:intlowerBound(vector<int>&nums,inttarget){intl=-1,r=nums.size();// 区间 (-1, n),哨兵可表示边界while(l+1<r){intmid=l+(r-l)/2;// 循环保证 r - l >= 2,mid 必在区间内if(nums[mid]>=target)r=mid;elsel=mid;}returnr;// 或 l + 1}vector<int>searchRange(vector<int>&nums,inttarget){intstart=lowerBound(nums,target);if(start==nums.size()||nums[start]!=target)return{-1,-1};intend=lowerBound(nums,target+1)-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)携带。

复杂度分析