leetcode34.排序数组中查找元素第一个和最后一个位置两种解题方法（超详细）

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=list&envId=ZCa7r67M这道题，读者可能会说这道题有什么好讲的？

不就是双指针一次就出结果吗？

本题我们将以双指针和二分查找两种思路讲解，并且着重讲解二分查找的方法，和其中的代码实现细节，喜欢看代码细节的读者可以耐心看一看，相信会有一定的收获。

第一种解法是双指针

思路：由于数组有序，呈递增状态，我们要找的是给定目标值target，在该数组内部出现的起始位置和终止位置，可以使用双指针从两边开始逐步探测，各指针都是只要找到target了，就停止寻找，直到两个位置都找到了target，就跳出，不用向里再寻找，此时的两指针指向位置正是答案，如果两指针指向一起也是正确的，因为可能target只出现了一次，如果循环结束还没找到结果（left<=right），那说明无法找到答案，返回{-1，-1}。

下面是可以通过的代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r){
            if(nums[l]==target&&nums[r]==target)return {l,r};
            if(nums[l]!=target)++l;
            if(nums[r]!=target)--r;
            
        }
        return {-1,-1};
    }
};

简洁的代码！你以为这就完了吗？判断的部分，也就是判断这两个位置对应元素是否都等于target这条代码一定要先写，不能写在先更改l或者r的后面，看起来逻辑没有什么不同，怎么写都对，但是实际上是有代码错误的，比如这条测试用例nums：[1] target： 0

虽然我们的判断逻辑是没问题的，但是先进行left和right的偏移，可能会使接下来的判断这两个位置对应元素是否都等于target这条代码出现越界错误。这是不容易被察觉到的错误，要小心。如果是先判断就不会有这样的错误，因为调整完left和right后，会进行的首先是越界判断，直接跳出循环了。

第二种解法二分查找

这一思路我用分别计算出左右边界的方法来讲解，这样写不容易出错，且思路清晰，代码有bug也更容易排查，强烈建议算法使用不是很熟练的读者使用这种写法。

解题思路就是分别求出左右边界，我讲其中之一，左边界，右边界与左边界思路是相同的，只是方向不同而已，稍加改动即可。

先给出代码根据代码进行分析

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=leftget(nums,target);
        int right=rightget(nums,target);
        if(left==-10||right==-10)return {-1,-1};
        if(right-left>1)return {left+1,right-1};
        return {-1,-1};
    }
    int leftget(vector<int>&nums,int target){
        int left=0,right=nums.size()-1;int res=-10;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]>=target){
                right=mid-1;res=right;
            }
            else left=mid+1;
        }
        return res;
    }
    int rightget(vector<int>&nums,int target){
        int left=0,right=nums.size()-1;int res=-10;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]<=target){
                left=mid+1;res=left;
            }
            else right=mid-1;
        }
        return res;
    }
};

细节非常多（只讨论left<=right）
把寻找左右界限分成了两个函数，然后求解
先看寻找边界的代码：
是用二分查找的方法写的，定义一个变量然后更新这个变量为返回值返回左右边界
寻找左边界，如果mid对应数据大于等于target将right左移，right=mid-1，大于target左移right天经地义，我们来看看等于时候
如果mid对应数据等于mid意味着什么？意味着我们要找的target范围数组就在此时的left——right之间，这个时候还左移right会使right最终移过target这片区域的最左端
正是这样，我们每一次进来，都更新左边界值为right。

几个疑问：
怎么确定right不断左移而最终会导致right走向target区域的左端点的？
其实整个过程不是通过一直的做right左移操作而使right一下子就确定了target区域的左端点的，而总是需要不停移left和right最终使right走向左端点
当mid对应数据大于等于target时候需要左移动right缩小范围，这时候target一定有全部或部分区域处在left——right这个范围内。
mid对应数据小于target也不一定就意味着target就一定不在范围内，可能是right移动完之后使得mid对应数据暂时小于target，这时候右移动left之后，可能会使mid对应数据重新大于等于target
如果是target不在left——right这种情境下，mid所取值一定是小于target了，所以left不停右移直到超出循环，而不会再更新最终target左窗口，也就是此时right的值。
上面的推论是保证right找到了左端点前一个位置时候，不会再乱动！

换句话说：当mid对应数据在target区间内时候，right每次更新为mid-1，也就是说只有两种可能right还是target，更新完right之后mid对应数据可能暂时性的小于targrt，但不要担心
我们调整left移动会最终使没走完的right继续左移动（这是mid由于right的缘故重新大于等于target）
如果上次mid指向的是起始点的target呢？那么right就指向了target区域的最左端点的左一个位置！！！这个时候mid一直会保持小于target
所以会一直右移动right，直到循环出去，不会更新数据，这也就是right为什么会保证一定处于target左端点前一个位置的重要原因！！
特例辩证：当right离边界很近的时候，left会不停缩减，直到仅剩一个元素，这个时候left和right所指那个元素一定是target，然后mid就是target，然后right向左移动
为什么一定指向right，假如left——right某时候只剩两个元素【0，1】而我们要找的是1，那么nums【0】==0会使left继续缩小范围
如果剩余的数据是【0，1，2】那也是一样的，right此时在0位置停下（说right离target边界近这个作为特例原因在于如果target离right远，比如在范围中间，那么肯定会正常的运行，如果很近那你可能不好想
为什么不会是right踩到边界然后退出循环，而是一定正好走到边界左一个位置？其实你举个例子就明白了）

为什么不先进行更新左边界再更新right？
因为没更新right之前，right此时的位置只能说明left——right中间的某位置确实是target所在的区域，而更新了right为mid-1，right此时就有可能作为target区域的左边界的左一个位置了
如果在不更新right时候去先更新最终答案，只会得到一个错误的答案，因为在最后一次左移动right数据时候，那个时候right可能处于target附近，那么这个时候就正好离我们要找的数据很近，
你可以调整返回值+1或者-1操作来通过一些用例，但是这并不能证明思路是正确的，这很可能是凑巧，并没什么逻辑性可言。
也很可能right离target很远，mid才是指向最后一个左端点位置，这个你找到的right一定是错误答案，这也就说明了如果你先更新最终要返回的边界数据，然后依赖于对这个数据+-1，调整
这是错误的想法，一开始我就对这个代码顺序进行了调整，因为我发现左右边界返回值始终都需要对左边界+1，右边界-1，所以萌生出先更新边界再更新right可能会得到简单的不需要后续处理的正确答案，
但实际上这种想法是十分愚蠢的。

左端点求解和右端点的求解很类似，它们是相同的思路，只不过方向不同而已，上面我们讲了左端点，就不再赘述右端点，类比一下就可以了
再来看有没有其他的问题，值得我们讲解。确实有一个而且是隐藏很深的问题。
在讲这个问题之前，先来看一些简单的，比如最后的处理数据方面，最后的处理数据返回答案方面，有三种情况需要讨论。
第一种是如果返回回来的值也就是左右边界其中之一为初始化时候的垃圾值，那么直接返回{-1，-1}这种情况是在说明target目标值范围处在整个给定数组的左边或者右边，简单地说就是出界了，
给定数组里不仅没有，而且也不可能有比如说给定数组是【1，2，3】而target为10，这种情况就是。
这种超边界的情况下，自己模拟一下代码就知道，求左边界时候，更新左边界的代码根本进不去，所以也就更新不了。它引出了我们后面要说的，为什么不把求解左右边界函数里的左右边界的初始化值
初始化为-1，这样不是更直观吗？这个我们放在后面讲解。

第二种情况是right-left>1才能进入真正的返回，也就是找到了答案子数组，有人会说这不对啊，为什么不是大于等于？这不会落下只有单独一个target的情况吗？
一开始我也是这么想，后来改代码测试一下，发现答案是错误的，
拿两种测试用例来分析
【1】【5,7,7,8,8,10】这两种，第一个target=1，第二个target=6，你会发现反倒是target=1这种看起来不可能过的用例通过了，但是其他的某些用例过不去。
这和返回值有关，你会发现它是先比较的左右边界返回值，而我们知道它的左右边界是要做处理的，比如【1】它的左右边界会返回【-1，1】而做了处理才会是真答案也就是【0，0】
所以不用担心这种target只有一个的，它也会正确输出，但是【5,7,7,8,8,10】target=6这种不一样，它代表了我们需要过滤出去的第二个错误情况，也就是给定数组的范围包含target，但实际上target不存在于
该数组中，这种情况会使得最终的left和right会缩在一起，因为它无法找到答案，但是target却确确实实的处在给定数组的范围内，以这个用例而言左边界的left和right会缩到1下标处也就对应数据7
然后mid过大，right移动向左，处在0这个位置上，跳出循环。而右边界是移动left然后取答案的，模拟可以知道，left和right都会处在7这个数据，然后right更新向左，右边界函数会返回此时left所在区域也就是1
这个下标，这样右边界减去左边界正好等于1，没错正好把错误的情况取答案了！所以不能写成大于等于1，而是大于1。
你可以这样想，如果左右边界取完差值等于1是什么情况（没做处理之前）？就是left和right在左右边界取时候，分别在没有找到target时候，交叉的越界，且距离为1。
这是典型的，target处在给定数组数据范围内，而不实际出现于给定数组中，请大家格外注意这种情况。
这种求解左右边界的代码如果遇到target只有1个的情况时候，会拉开距离返回去，也就是说，一定会在target下标的左右偏移1的位置出现，也就是说一定大于1，只有target有0个时候，才会拉不开距离相减等于1

第三种情况是直接返回{-1，-1}这种情况对应的其实就是情况二里找不到时候，应该返回的【-1，-1】因为上面我们分析的是为什么不写>=1，这个等于1就是错误答案，在后面返回-1就可以了
取到正确答案时候，在情况二中返回正确序列即可。

最后我们终于可以说到这个隐晦错误了，为什么左右边界函数边界返回值不能初始化为-1？
这个是由测试用例【1】这种类型引起的错误，当target只有1个，而且target在左边界时候，就会出现左边界取到-1，这个时候如果你的边界初始化就是-1，且以该值作为错误答案判断依据时候
就会发生错误，原本正确的解被丢弃。所以我们初始化应该取一个除了小于0且不等于-1的数，从这些里初始化值就正确了，

至此把所有疑点全部讲解完毕。

还有就是最后的判断部分读者可能感觉有点奇怪，考虑对返回答案做一些适当的调整，不过不要忘记对可能出错误的判断部分做出调整，主要是：对于target不在数组内部和target在数组范围但是不在数组里
这两种情况，做出调整后，题解依然正确。

给出一个更改后的示例代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=leftget(nums,target);
        int right=rightget(nums,target);
        if(left==-9||right==-11)return {-1,-1};
        if(right-left>=0)return {left,right};
        return {-1,-1};
    }
    int leftget(vector<int>&nums,int target){
        int left=0,right=nums.size()-1;int res=-10;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]>=target){
                right=mid-1;res=right;
            }
            else left=mid+1;
        }
        return res+1;
    }
    int rightget(vector<int>&nums,int target){
        int left=0,right=nums.size()-1;int res=-10;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]<=target){
                left=mid+1;res=left;
            }
            else right=mid-1;
        }
        return res-1;
    }
};

本期内容就到这里

如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注