题目描述:
给定一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
示例 1:
输入:nums = [5,7,7,8,8,10],target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10],target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
解决方案:
1、分析题目:非递减排列的数组,即顺序为从小到大且存在相同值
2、二分法查找只能找到一个定值,不能确定相同值的多个位置,故需要把问题答案进行适当转换
3、寻找目标值第一次出现的位置==> 比目标值小的范围内,最大的数 的位置 +1 即不大于目标值
4、最后一次出现的位置==> 大于目标值的范围内,最小数的位置-1
函数代码:
class Solution { public: int lower_bin(vector<int>& nums,int target){ int left=0,right=nums.size()-1,mid; while(left<=right){ mid=left+(right-left)/2; if(nums[mid]>=target){ right=mid-1; }else{//返回第一个小于这个数的值 left=mid+1; } } return left; } int upper_bin(vector<int>& nums,int target){ int left=0,right=nums.size()-1,mid; while(left<=right){ mid=left+(right-left)/2; if(nums[mid]>target){//返回第一个大于这个数的值 right=mid-1; }else{ left=mid+1; } } return right; } vector<int> searchRange(vector<int>& nums, int target) { if(nums.empty()) return vector<int>{-1,-1}; int lower=lower_bin(nums,target); int upper=upper_bin(nums,target); if(lower==nums.size()||nums[lower]!=target){ return vector<int>{-1,-1}; } return vector<int>{lower,upper}; } };