当前位置：首页 > article >正文

备战蓝桥杯：二分算法详解以及模板题

article 2025/2/11 15:09:42

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

像这种题，要找一个值出现的起始位置和终止位置，我们可以用暴力解法，这时候时间复杂度是O（N）

为了优化，我们要学一下二分的算法

1.查找起始位置：

比如我们查找2的起始位置，我们可以把数组一分为二，一部分是小于2的，一部分是大于等于2的，我们初始化left和right指针，left=1，right=n，然后我们找mid，如果mid的值在大于等于2的里面，我们就让right移动到mid这里，如果是小于2，我们就让left移动到right+1的位置里

当然，我们要处理很多细节问题，第一个问题，循环判断条件

我们是用left<right 还是left <= right 呢？我们举个例子吧

如果mid大于等于2，right=mid

然后left和right相等继续进入循环，又让right=mid，陷入死循环了

所以我们应该是用left<right来判断，如果相等的话就结束了，有可能就是我们查找的结果

求中点的方式

我们可以用（left+right）/2 求中点，如果是偶数个的话中点偏左

也可以用（left+right+1）/2来求中点，如果是偶数个的话中点偏右

我们求起始位置的时候，因为起始位置在左边，应该用第一个，如果用第二个

就会陷入死循环

第三个细节问题就是结束后指针位置是不是最后结果了

如图，t=2，left就会指向1，这时候也不是最后答案所以我们查询失败，查询到的仅仅是比2小的最大的数了

2.查询终止位置

查询终止位置，我们数组可以分为小于等于t和大于t两部分

初始化left和right指针，如果mid指向的值大于t，我们就让left=mid-1，如果mid指向的值小于等于t，我们就让left=mid，

好的，我们直接来处理一下终止位置的细节问题

1.判断循环条件

依旧是left<right进入循环，因为

如图，mid的值小于等于2，让left移动到mid位置，接下来left等于right，中点还是这个位置，那么该位置还是小于等于2，还让left移动到mid这里，就是死循环了

2.处理求中点的方式

因为我们求终止位置，中点位置应该是靠右的，所以应该是（left+right+1）/2

如果中点求的是靠左边的话，依旧是会陷入死循环

好，闲话少唠，我们来实现一下代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 0) return {-1,-1};
        int left = 0,right = n-1;
        //求起始位置
        while(left<right)
        {
            int mid = (left+right)/2;
            if(nums[mid]>=target) right = mid;
            else left = mid+1;
        }
        if(nums[left] != target) return {-1,-1};
        int retleft = left;
        left = 0,right = n-1;
        while(left<right)
        {
            int mid = (left+right+1)/2;
            if(nums[mid]<=target) left = mid;
            else right = mid-1;
        }
        return {retleft,left};
};
};

关于时间复杂度的话，假设我们的执行次数是x，

总长度是n n/2/2/2/2/..../2=1 执行一次除一次2，一共除x次2，所以 2的x次方等于n，x就是logN

时间复杂度就是logN

我们还要介绍一种防溢出的写法，比如我们的（left+right）/2的时候，如果left和right都很大，加起来可能超过int，这时候我们可以写成 left+（right-left）/2 的形式，通分之后是2分之2*left+2分之right-left 结果还是（left+right）/2 同理也可以把(left+right+1)/2 换成 left+(right-left+1)/2，好的，我们也可以直接写成long long

最后的最后，我们来介绍一下stl里的二分，upper_bound和lower_bound,lower_bound返回有序数组里大于等于t的最小元素，upper_bound表示大于t的最小元素，