首页 > 招聘信息 > 吃透二分法——二分系列经验分享

吃透二分法——二分系列经验分享

头像
算法小爱
发布于 2021-07-27 10:11:02 APP内打开
赞 1 | 收藏 1 | 回复0 | 浏览143

吃透二分法

大家好,这里是GTA小分队。这一周的时间,我们对很早之前分享过的二分算法文章进行了大量修改和补充,希望能使大家对二分法的基本原理和应用有更深的了解。

二分法是典型算法,分为基础的二分搜索和进阶的二分答案。一般而言,是利用序列的有序性将 的搜索复杂度降至 ,以提升算法效率的方法。本文将详细介绍这两类问题,并给出通用的代码框架。本文的思维导图如下:

二分思维导图

二分搜索

猜数问题

图片说明

游戏 选定一个 之间的数让 猜,每次 告知 猜的数比选定的数大还是小,然后 继续猜,直到猜到选定的数。

在这个问题中,如果 每次都猜当前可能范围 的中点 ,可以在最少的次数内猜到选定的数。每次根据 的反馈调整范围的上/下边界,由于每次都是猜的中点,所以每一次的调整都能将范围缩小一半,这样可以在 次内猜中 选定的数。

这一策略便是最基本的二分思想:首先确定搜索范围,每一轮先取当前范围中点,然后判断其和目标 的关系,以决定下一次调整范围的方向。在每次调整范围后,要判断新的范围是否合法,再进行下一轮搜索。

基于猜数问题,我们给出二分搜索的基本框架:

int l = 1, r = 100; // 初始搜索范围
int ans = 0; // 记录结果
while(l <= r) {
    int mid = l + (r - l) / 2; 
    if(mid == target) {
        ans = mid;
        break;
    } else if(mid > target) { // 数组有序,应向前查找
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}

需要注意的是,二分法有多种框架,差别主要体现在两处,一处是 while 语句的判定条件,一处是搜索范围转移的方式。有的框架可能使用 while(l < r)r = mid, l = mid + 1 结合的方式,与本文框架使用的 while(l <= r)r = mid - 1, l = mid + 1 结合的方式在结果上是基本一致的,只不过本文给出的框架较为对称,更便于记忆,且不需要根据问题的不同而转化搜索范围转移的方式,具有更好的通用性

另一方面,上面第 行代码中使用了 而非 ,是为了防止溢出。当 均达到对应变量类型的上限数量级时,直接求和可能导致突破上限溢出,而通过代码中的计算方式则可以避免这个问题。

第一个/最后一个

二分搜索的简单应用可以参考 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置:给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

本题与猜数问题有两个不同点。

第一个不同点在于,猜数问题是直接用计算出的 作为本次比较的数;而本题计算出的 是序列中的位置,需要比较的是 的关系。

第二个不同点在于,猜数问题只要找到目标元素,便可以退出二分过程。但对于本题而言,找到目标元素时,不能保证这就是第一个/最后一个出现的位置,所以要继续调整范围进行下一轮搜索。

举个例子,比如我们在数组 中寻找 第一个出现的位置,那么我们第一次二分找到的是中间那个 。我们知道,要么这个 就是第一个出现的 (此时我们更新结果位置 为当前位置),要么在它之前还有 出现(此时我们需要在 范围内继续搜索)。

int ans = -1; 
// 设定为 -1 是为了防止“没有任何一个满足条件的解” 的情况
// 此时可以通过比较 ans 与 -1 的关系进行处理
while(l <= r) {
    int mid = l + (r - l) / 2; 
    if(a[mid] == target) {
        r = mid - 1; 
        // 如果寻找最后一个位置,此时应提高下界:l = mid + 1
        ans = mid;
    } else if(a[mid] > target) {
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}

标准库函数

对于基础的二分搜索,++ 还提供了两种基于标准库 的实现方式:

ForwardIter lower_bound(ForwardIter first, ForwardIter last, const _Tp& val) 返回一个序列 中第一个大于等于位置

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val) 返回一个序列 中第一个大于位置

我们还以上面的问题作为例子,在寻找目标元素 第一次出现的位置时,我们使用 lower_bound 函数:

int ans = lower_bound(a.begin(), a.end(), target) - a.begin();

这里由于lower_bound()函数返回的是一个迭代器,减去同为迭代器的 后,才是要求的位置。

另外,由于 lower_bound()函数找的是第一个大于等于某值的位置,所以如果序列中不存在值为 的元素,该函数将返回第一个大于该值的位置。所以还要进行额外判断。

当我们求目标元素 最后一个出现的位置时,可以利用 lower_bound() 函数找到第一个大于等于 的位置,然后减去一,便找到了 最后一个可能出现的位置(这里的可能考虑到了序列中没有值为 的元素的情况)。

二分答案

在一些较为复杂的最值问题中,我们可能无法一下子想出来好的算法。而通过枚举法检验所有可能的解并不现实,因为时间复杂度过高。在解空间有序的情况下,我们可以尝试通过二分搜索构造可能解,并根据其合法与否(也即是否能满足题目要求)调整搜索范围,以对数级的时间复杂度找出最值解。这种策略一般称为二分答案。

图片说明

check函数

上面说到,在二分答案问题中,需要判断构造出可能解的合法性。一般地,我们通过引入一个 check() 函数来完成这件事。

check() 函数一般为布尔型函数,如果当前解合法则返回 true,否则返回 false。程序根据 check()函数的返回值来调整下一轮二分搜索的搜索范围,而具体 truefalse 分别如何调整,是根据不同题目有所改变的。但是一般来说,这两种返回值对应的范围调整策略是不同的。

为了便于理解,我们给出通用的二分答案代码框架:

while(l <= r) {
    int mid = l + (r - l) / 2; 
    if(check(mid)) {
        update_range_1();
    } else {
        update_range_2();
    }
}

几道例题

为了使大家更好的理解和应用二分答案策略,我们一起来看几道例题,并按照一定的套路来分析和解决这些题目。

首先我们来看 LeetCode 1011. 在 D 天内送达包裹的能力:传送带上的包裹必须在 天内从一个港口运送到另一个港口。包裹重量通过一个数组 给出。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。求能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

第一步,确定初始范围

本题要求运载能力,由于我们的运载能力一定大于等于最重的一个包裹,所以将最小值设定为 ;而最大值设定为 ,此时可以一天内运送完成

第二步,完善 check()函数。

然后,我们通过 **构造出可能的运载能力 **,代入 check() 函数中判断是否合法。

由于题目要求要在 天内送达,所以我们判断合法的依据就是当前构造的运载能力能否在 天内送达所有包裹。由于题目要求按数组顺序传送包裹,所以我们利用贪心算法,若当前累加的包裹重量大于运载能力,则天数 加一。最终判断总天数 即可。

bool check(int capability, vector<int>& weights, int D) {
    int sum = 0, days = 1;    // 初始化当前重量tmp,当前天数为1天
    for(auto wt : weights) {
        if(sum + wt > capability) {    // 超过当前承载力,说明需要第二天运送,tmp初始化为wt
            days++;
            sum = wt;
        } else {
            sum += wt;    // 未超过,更新当前重量
        }
    }
    return days <= D;
}

第三步,考虑搜索范围转移。

check()函数返回为 false 时,说明当前构造的解不合法,也即无法在 天内传送完所有的包裹,也即当前构造的运载能力较小,需要提高下界,在 范围内继续搜索。若返回 true,说明当前构造的解合法,由于本题要求最低运载能力,也即最小合法解,所以我们要降低上界,在 范围内搜索是否有更小的合法解。代码如下:

int shipWithinDays(vector<int>& weights, int D) {
    int maxweight = 0, sum = 0, ans = 0;
    for(auto wt : weights) {
        maxweight = max(maxweight, wt);
        sum += maxweight;
    }
    int l = maxweight, r = sum;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid, weights, D)) {
            ans = mid; // 更新当前最小的合法解
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

下面我们来看 LeetCode 719. 找出第k小的距离对:给定一个整数数组,返回所有数对之间的第 个最小距离。数对 的距离定义为两数之差的绝对值,也即

第一步,确定初始范围

本题要求的是距离,其最小值一定为 ,最大值可以设定为数组中值相差最大两个元素的距离,而这可以通过先对数组进行排序得到。考虑到本题的数据范围,可以在 复杂度内运行完成。

第二步,完善 check()函数。

本题**构造的是可能的第 个最小距离,所以我们判断合法的依据为:是否有至少 个数对的距离小于等于当前构造解**。由于已经对数组进行了排序,所以我们可以利用双指针法在 的复杂度内进行判定:

bool check(int dist, vector<int>& nums, int k) {
    int n = nums.size(), j = 1;
    int cnt = 0; // 记录小于等于当前构造解 dist 的距离对数量
    for(int i = 0; i < n; i++) {
        while(j < n && nums[j] <= nums[i] + dist) j++;
        cnt += j - i - 1; // 处于 [i + 1, j] 中的数与 a[i]的距离均小于 dist
    }
    return cnt >= k;
}

第三步,考虑搜索范围转移。

check()函数返回为 false 时,说明当前构造的解不合法,也即小于等于当前构造解的距离对数量小于 个,也即当前构造的距离较小,需要提高下界,在 范围内继续搜索。若返回 true,说明当前构造的解合法,由于本题要求的是第 个最小距离,也即最小合法解,所以我们要降低上界,在 范围内搜索是否有更小的合法解。代码如下:

int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int l = 0, r = nums[n - 1] - nums[0];
    int ans = 0;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid, nums, k)) {
            ans = mid; // 记录当前最小合法距离
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

最后我们来看 LeetCode 1552. 两球之间的磁力:给定数组 表示 个篮子的位置,把 个球放入其中的 个篮子中,若两球分别处于 的两个篮子中,它们之间的磁力定义为 ,要求最大化最小磁力。

之前已经进行过了两道题的分析,我们直接按套路来~

第一步,确定初始范围

本题要求的是磁力,由于磁力定义为两个球之间距离的绝对值,那么最小磁力一定是所有篮子中间隔最小的距离,通过遍历所有篮子位置即可得到;最大磁力一定在平均放置所有小球的情况下取到,相当于在两边的篮子()中间放置 个小球( 个间隔),最大磁力就与间隔的长度相同。故有:
$$
第二步,完善 check()函数。

本题构造的是可能的最小磁力,所以判断合法的依据便是:是否存在一种放置小球的方式,使得全部相邻小球之间的磁力均大于等于我们构造出的可能解。也即,当我们以构造出的可能解作为磁力最小阈值时,放置的小球数量是否大于等于 个(若小于 个,说明当前构造出的最小磁力过大,不满足题意,当能放置大于等于 个小球时,我们不妨只放置 个小球,此时一定满足题意要求)。

我们最终希望放置尽可能多的小球,所以我们以贪心法遍历所有的篮子,并利用一个变量 记录上一个小球放置的位置。如果当前篮子位置与上一个小球放置的位置已经大于等于构造解了,我们就在此处放一个小球。代码如下:

bool check(vector<int>& position, int dist, int m) {
    int prev = position[0], cnt = 1;
    for(int i = 1; i < position.size(); i++) {
        if(position[i] >= prev + dist) {
            prev = position[i];
            cnt++;
        }
    }
    return cnt >= m;
}

第三步,考虑搜索范围转移。

check()函数返回为 false 时,说明当前构造的解不合法,也即当前磁力过大,不能作为最小磁力,需要降低上界,在 范围内继续搜索。若返回 true,说明当前构造的解合法,由于本题要求的是最大的最小磁力,也即最大合法解,所以我们要提高下界,在 范围内搜索是否有更大的合法解。代码如下:

int maxDistance(vector<int>& position, int m) {
    int l = INT_MAX, r = 0;
    int n = position.size();
    sort(position.begin(), position.end());
    for(int i = 0; i < n - 1; i++) {
        l = min(l, position[i + 1] - position[i]);
    }
    r = (position[n - 1] - position[0]) / (m - 1);

    int ans = 0;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(position, mid, m)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

总结

本文从猜数问题入手,给出了二分法的基本框架;通过第一个/最后一个问题,阐述了搜索范围转移的思考过程;通过 标准库 函数帮助大家更方便的解决二分搜索的基本问题;在二分答案专题中,我们先介绍了 check() 函数的意义和构造思路,并通过 几道例题 梳理了解决问题的步骤和思考方式。

二分法是典型的算法,在笔试面试中也常常出现。希望这篇文章能帮助大家更加熟练的了解和掌握二分法,如果有疑问,欢迎后台留言提问,或公众号后台回复【进群】加入刷题群一起讨论!


我们是GTA小分队,一群就读于人大、北航、北理等学校的计算机专业本科生和研究生。我们的公众号【GTAlgorithm】专注于算法专题、比赛题解、大厂面经的分享,目前已有 篇原创作品,致力于陪大家一起收割大厂offer。

欢迎大家点亮【赞】和【在看】,也欢迎【分享】给身边的小伙伴。后台回复【进群】可加入刷题群,回复【面经】可获得真实大厂面经(附带答案)

点击查看原文

0条回帖

回帖
加载中...
话题 回帖

推荐话题

相关热帖

招聘信息近期热帖

近期精华帖

热门推荐