这是一个研究二分法的高级主题。查找排序数组中元素的第一个和最后一个位置给定一个按升序排列的整数数组nums和一个目标值target。找出给定目标值在数组中的开始和结束位置。如果数组中不存在目标值target，则返回[-1,-1]。进阶：你能设计并实现一个时间复杂度为O(logn)的算法来解决这个问题吗？示例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]如果这道题的基础不是很好，那就不行建议阅读短代码。简短的代码隐藏了太多的逻辑。细节！对bifen不了解的同学，先做这两道题：704.二分查找35.查找插入位置所有情况我来讨论一下。在数组中查找目标的左右边界，有以下三种情况：情况一：目标在数组范围的右边或左边，例如数组{3,4,5}，则target为2或数组{3,4,5}，target为6，此时应返回{-1,-1}。情况2：目标在数组范围内，数组中没有目标，例如数组{3,6,7}，目标为5，应该返回{-1,-1}情况3：目标在数组范围内，数组中有目标，例如数组{3,6,7}，目标为6，应返回{1,1}此时。三种情况都算Arrived，解释的很清楚了。接下来，寻找左边界和右边界。用二分法求左右边界。为了代码清晰，我写了两个二分法来求左右边界。刚接触二分查找的同学不推荐。就像如果用二分查找左右边界的话，很容易让自己卷入其中。建议扎扎实实的写两个二分查找，分别求左边界和右边界。先找到正确的边界。边界，关于二分查找，如果你看过704.二分查找，你就会知道二分查找什么时候用while(left<=right)，什么时候用while(left&nums,inttarget){intleft=0;intright=nums.size()-1;//在左闭右闭区间定义target，[left,right]intrightBorder=-2;//记录rightBorder未赋值的情况while(left<=right){//当left==right时，区间[left,right]仍然有效intmiddle=left+((right-left)/2);//防止溢出相当于(left+right)/2if(nums[middle]>target){right=middle-1;//target在左区间，所以[left,middle-1]}else{//当nums[middle]==target时，更新left，这样就可以得到target的右边界。target)//如果leftBorder没有赋值（即target在数组范围的右边，比如数组[3,3]，target为4），intgetLeftBorder(vector&nums,inttarget){intleft=0;intright=nums.size()-1;//在左闭右闭范围内定义target，[left,right]intleftBorder=-2;//记录leftBorder没有赋值的情况while(left<=right){intmiddle=left+((right-left)/2);if(nums[middle]>=target){//要找到左边界，当nums[middle]==target时更新right=midle-1;leftBorder=right;}else{left=middle+1;}}returnleftBorder;}处理完三种情况，计算出左右边界，再看主要代码。这里，上面讨论的三种情况都在classSolution{public:vectorsearchRange(vector&nums,inttarget){intleftBorder=getLeftBorder(nums,target);intrightBorder=getRightBorder(nums,target);//case一个if(leftBorder==-2||rightBorder==-2)return{-1,-1};//案例三if(rightBorder-leftBorder>1)return{leftBorder+1,rightBorder-1};//案例二return{-1,-1};}private:intgetRightBorder(vector&nums,inttarget){intleft=0;intright=nums.size()-1;intrightBorder=-2;//记录rightBorder没有赋值的情况while(left<=right){intmiddle=left+((right-left)/2);if(nums[middle]>target){right=middle-1;}else{//找到右边界，当nums[middle]==target时更新leftleft=middle+1;rightBorder=left;}}returnrightBorder;}intgetLeftBorder(vector&nums,inttarget){intleft=0;intright=nums.size()-1;intleftBorder=-2;//记录是否有没有leftBorder被赋值的情况while(left<=right){intmiddle=left+((right-left)/2);if(nums[middle]>=target){//寻找左边框，更新rightright=middle-1;leftBorder=rightwhennums[middle]==target;}else{left=middle+1;}}returnleftBorder;}};这段代码非常简洁优化空间很大，比如将搜索左右区间函数合并在一起，拆开更清晰，将三种情况及对应的处理逻辑完整呈现。Summary初学者建议你把这道题一块一块地拆分。如本题解答所述，想通三种情况后，先着重寻找右区间，再着重寻找左区间，最后根据左右区间做出判断。千万不要上来就想，如果把左右间隔一起找，就会不见一个，丢一个，绕一圈就拉不出来了。其他语言版本JavaclassSolution{int[]searchRange(int[]nums,inttarget){intleftBorder=getLeftBorder(nums,target);intrightBorder=getRightBorder(nums,target);//案例一if(leftBorder==-2||rightBorder==-2)returnnewint[]{-1,-1};//案例三if(rightBorder-leftBorder>1)returnnewint[]{l??eftBorder+1,rightBorder-1};//案例二returnnewint[]{-1,-1};}intgetRightBorder(int[]nums,inttarget){intleft=0;intright=nums.length-1;intrightBorder=-2;//记录rightBorder没有赋值的情况while(left<=right){intmiddle=left+((right-left)/2);if(nums[middle]>target){right=middle-1;}else{//找到右边界，当nums[middle]==target时更新leftleft=middle+1;rightBorder=left;}}returnrightBorder;}intgetLeftBorder(int[]nums,inttarget){intleft=0;intright=nums.length-1;intleftBorder=-2;//记录leftBorder没有赋值while(left<=right){intmiddle=left+((right-left)/2);if(nums[middle]>=target){//寻找左边界的情况，当nums[middle]==时更新目标右t=middle-1;leftBorder=right;}else{left=middle+1;}}returnleftBorder;}}//方案2//1.首先在nums数组中查找binary中的target；//2.如果二分查找失败，binarySearch返回-1，表示nums中没有目标。这时候searchRange直接返回{-1,-1}；//3。如果二分搜索成功，则binarySearch返回nums下标中target的值。然后左右滑动指针，找到区间classSolution{publicint[]searchRange(int[]nums,inttarget){intindex=binarySearch(nums,target);//二分查找if(index==-1){//nums中没有target，直接return{-1,-1}returnnewint[]{-1,-1};//匿名数组}//nums中有target，然后左右滑动指针找到匹配题Interestedintervalinleft=index;intright=index;//向左滑动找到左边界while(left-1>=0&&nums[left-1]==nums[index]){//防止数组越过边界。逻辑短路，两个条件的顺序不能改变left--;}//向左滑动找到右边界while(right+1List[int]:defgetRightBorder(nums:List[int],target:int)->int:left,right=0,len(nums)-1rightBoder=-2#记录rightBorder没有赋值的情况whileleft<=right:middle=left+(right-left)//2ifnums[middle]>target:right=middle-1else:#寻找右边框,nums[middle]==targetupdateleftleft=middle+1rightBoder=leftreturnrightBoderdefgetLeftBorder(nums:List[int],target:int)->int:left,right=0,len(nums)-1leftBoder=-2#如果没有leftBorder则记录被赋值的情况whileleft<=right:middle=left+(right-left)//2ifnums[middle]>=target:#寻找左边界，updateright=middle-1;leftBoder=whennums[middle]==目标正确；埃尔se:left=middle+1returnleftBoderleftBoder=getLeftBorder(nums,target)rightBoder=getRightBorder(nums,target)#案例一ifleftBoder==-2orrightBoder==-2:return[-1,-1]#案例三ifrightBoder-leftBoder>1:return[leftBoder+1,rightBoder-1]#情况2return[-1,-1]#Solution2#1。首先，二分查找nums数组中的目标；#2。如果二分查找失败，binarySearch返回-1，表示nums中没有目标。这时候searchRange直接返回{-1,-1}；#3。如果二分查找成功，binarySearch返回一个下标，其值为nums中的target。然后左右滑动指针，找到区间classSolution:defsearchRange(self,nums:List[int],target:int)->List[int]:defbinarySearch(nums:List[int],target:int)->int:left,right=0,len(nums)-1whileleft<=right:#不变量：左闭右闭区间middle=left+(right-left)//2ifnums[middle]>target:right=middle-1elifnums[middle]=0andnums[left-1]==target:left-=1#向右滑动，找到右边界whileright+1List[int]:defbinarySearch(nums:List[int],target:int,lower:bool)->int:left,right=0,len(nums)-1ans=len(nums)whileft<=right:#不变量：左闭右闭区间middle=left+(right-left)//2#lower是True，执行前半部分，找到第一个大于等于target的下标，否则找到第一个大于target的下标ifnums[middle]>targetor(lowerandnums[middle]>=target):right=middle-1ans=middleelse:left=middle+1returnansleftBorder=binarySearch(nums,target,True)#搜索左边界rightBorder=binarySearch(nums,target,False)-1#搜索右边界ifleftBorder<=rightBorderandrightBorderList[int]:defbinarySearch(nums:List[int],target:int)->int:left,right=0,len(nums)-1whileleft<=right:#Invariant:left-closedright-closedintervalmiddle=left+(right-left)//2ifnums[middle]>=target:right=middle-1else:left=middle+1returnleft#如果target存在，返回第一个等于target的值leftBorder=binarySearch(nums,target)#搜索左边界rightBorder=binarySearch(nums,target+1)-1#搜索右边界ifleftBorder==len(nums)ornums[leftBorder]!=target:#case1和case2return[-1,-1]return[leftBorder,rightBorder]
