解锁“二分魔法”：让算法题轻松找到答案的秘密（2）

解锁“二分魔法”：让算法题轻松找到答案的秘密（2）

前言：

在算法的世界里，二分法被誉为“魔法”般的存在。这种简单而强大的工具，能够在庞大的解空间中快速找到答案，尤其在复杂的算法题中，往往能化繁为简，带来突破性的思路。然而，掌握二分法不仅仅是了解“左右边界”这么简单，它的精髓在于将问题抽象为“单调性”，进而进行有效的搜索。本文将继续带你解锁二分法的进阶技巧，从实际问题出发，剖析隐藏在算法题背后的二分“魔法”，让你在解题时游刃有余，轻松找到答案！

小编在前文讲述了二分算法的第一个题目，同样也是二分算法的第一个模版，今天小编紧接着上文所说，开始讲述二分算法余下的两个模版，下面开启今日的做题之旅~

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

1.1.题目来源

本题和之前的题目一样，源自于力扣，下面小编给出它的链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

1.2.题目解析

本题是给了我们一个非递减排列的数组以及一个目标值，想让我们在这个数组里面找到一个区间，这个区间里面的数都是目标值所在的数，我们仅需返回它刚开始出现的位置以及结束的位置即可，如果在这个数组里面没有这个数，那么就返回-1和-1即可，为了让各位更好的理解，下面小编就以示例一为例，示例一是想让我们在数组中找到连续8的区间，此时8开始位置是3，所以左边界是3，结束位置是4，所以右边界就是4，此时我们就找到了8所在的区间，就是[3,4]，本题就是想要我们实现找到一个数的左边界和右边界，下面小编进入本题目的思路讲解。

1.3.题目思路讲解

通过小编前面讲述的题目解析后，相信部分读者朋友已经知道了本题目的大致内容，此时我们需要分两步来进行本题目的完成，第一步是寻找左端点，第二步是寻找右端点，在这两步中，我们分别可以知晓其中的“二分性”，下面小编先通过左端点的寻找来告诉各位如何寻找左端点。

1.左端点

​

对于左端点的寻找，我们往往可以分为两个区间进行查找，如上图所示，第一个区间是小于target的部分，第二个区间是大于等于target的部分，这么分的原因是因为此时我们要寻找左端点，左端点是第一个出现的位置，所以我们应该从右边找第一个出现的位置，这样的话寻找起来是比较容易的，此时对于本题目，我们同样也可以设置好两个“指针”，一个在开头，一个在结尾，还需要一个中间值mid，此时的mid求解起来其实是有一个小坑的，对于mid的求法，我们知道有两种方法可以求解mid，如下所示：

​ 前者代表的是中间值在右边，后者表示中间值在左边，对于这二者如何使用，等小编讲述左端点的求法的时候，会着重强调这里，下面我们继续左端点求法的详解。

设置完三个元素后，我们就要开始寻找此时的左端点，我们先求出mid，求完后我们和target进行比较，如果mid大于等于target的话，证明此时的左端点在包含mid的左半边区域，所以此时我们右边的边界变为mid，因为此时mid的值可能会出现等于target的情况；如果此时mid位置的值要小于target，那么说明mid左边的区间不会存在等于target的情况，此时我们就让左区间变为mid + 1即可，至于为什么不是mid，因为mid位置的值肯定要小于target，此时我们通过循环的查找，最后就会寻找到左端点，当然，对于寻找不到的情况如何分辨，我会在代码的讲解中叙述的，此时我们需要知道一个问题，此时的mid到底是选用1还是选用2，下面小编分别进行尝试：

如果此时我们选择1作为中间值的求法，假设此时我们目前只有两个值进行查询，如下图所示：

此时我们如果采取1的方法，那么此时的right就是mid，如果此时mid的数据恰好是小于等于我们要查找的target，那么此时我们就需要让right变为我们的中间值，此时我们再去求解mid的时候，此时我们就会陷入一个循环，因为mid还好会到right的位置重复刚才的操作，所以此时的选择1就不可以了，不过此时的选择2就可以避免这种情况，这里我就不多说了，相信各位小伙伴是会根据选择1推选择2的，所以此时我们就找到了左端点，下面我们继续去寻找右端点。

2.右端点

右端点的查找和左端点是相似的，我们仍需划分出两端区间，第一段区间是小于等于目标值的区间，第二段区间是大于目标值的区间，此时我们依然是需要求解中间值，此时求解中间值的方法用到的是解法1，对于它的证明小编就不详细说了（不知晓的读者朋友可以私信询问我），之后我们依然是设置好三个元素，两个指针（left和right），一个中间变量mid，此时我们依旧是先去寻找中间变量，与中间变量进行比较，小编感觉文字书写有点死板，于是我用伪代码的方式给各位进行讲解：

while(left < right)  //等于的话会出现死循环
{
    int mid = left  + (right - left + 1) / 2;
    if(num[mid] <= target) left = mid;//此时因为右端点可能就在左边的区间内，所以此时我们仅需让左段到mid即可
    if(nun[mid] > target) right = mid - 1;  // 因为此时的右端肯定没有右端点，所以让right到mid左边即可。
}

此时我们就求解完了左端点和右端点，下面小编讲述其的代码实操。

1.4.代码教学

首先，我们需要先避免一个小坑，因为此时的数组可能就是个空的，所以我们要判断此时的数组是否为空，如果为空的话，我们直接返回{-1，-1}即可，之后我们在设置好需要的工具先寻找左端点即可：

//先判断数组为空
if(nums.size() == 0)
return {-1,-1};
//先找左端点。
int left = 0,right = nums.size() - 1,mid = 0,begin = -1,end = -1;

之后我们需要进入循环去寻找左端点，循环的条件自然是left<right，之后就根据我上面说的，寻找左端点即可：

while(left < right)
{
    mid = left + (right - left) / 2;
    if(nums[mid] < target)
    {
        left =  mid + 1;
    }
    else
    {
        right = mid;
    }
}

寻找完左端点以后，按理说我们需要保存左端点，但此时可能会出现一个情况：此时的左端点不存在，即为-1，所以我们先判断此时的左端点是否为-1，如果为-1的话，我们直接返回{-1，-1}即可。

if(nums[left] == target)
begin = left;
if(begin == -1)
return {-1,-1};

之后我们就要开始进行右端点的查找，其查找的方式和我伪代码写的很像，所以小编就不详细介绍了：

//在找右端点
right = nums.size() - 1;
while(left < right)
{
    mid = left + (right - left + 1) / 2;
    if(nums[mid] > target)
    {
        right = mid - 1;
    }
    else
    {
        left = mid;
    }
}

之后我们无须判断此时的右端点是否存在了，因为此时的左端点已经存在，最差的情况顶多就是左端点和右端点重合了，所以我们保存好数据直接返回即可。

end = right;
return {begin,end};   

1.5.代码展示

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //先判断数组为空
        if(nums.size() == 0)
        return {-1,-1};
        //先找左端点。
        int left = 0,right = nums.size() - 1,mid = 0,begin = -1,end = -1;
        while(left < right)
        {
            mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left =  mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        if(nums[left] == target)
        begin = left;
        if(begin == -1)
        return {-1,-1};
        //在找右端点
        right = nums.size() - 1;
        while(left < right)
        {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid;
            }
        }
        end = right;
        return {begin,end};   
    }
};

1.6.最后的两个模版

最后，小编告诉各位二分查找算法我已知的最后两个模版，分别是查找左端点的模版和查找右端点的模版，下面小编分别展示：

1.左端点模版

while(left < right)
{
    mid = left + (right - left) / 2;
    if(nums[mid] < target)
    {
        //。。。。就题目分析
    }
    else
    {
        //。。。就题目分析
    }
}

2.右端点分析

while(left < right)
{
    mid = left + (right - left + 1) / 2;
    if(nums[mid] > target)
    {
        //........
    }
    else
    {
        //...............
    }
}

2.总结

本文到这里也就结束了，小编先自我批评一下，我认为这篇文章我写的很烂，主要是因为相隔时间太久写的，依稀记得，本文我是在11月中旬写的，现在我写完的时间是十二月初，隔了很长时间，有些内容我都忘了，所以可能有的地方衔接不上，恳请各位读者见谅，如有意见，放到评论区批评我即可，一起写题的时光总是很短暂的，那么各位大佬们，我们下一期再见啦！