二分法 – MiyanLog

概述

二分法是一种非常常用的优化技巧，它可以分为二分查找、二分答案、浮点数二分和三分法等。

先从一个猜数字游戏来引入二分，猜一个 \(1\) ~ \(100\) 的数字：

有些聪明的小朋友肯定是先从 \(50\) 开始猜；
为什么从 \(50\) 开始猜呢？因为这样可以排除一半的数字，如果小了就说明答案在 \(51 \)~ \(100\) 的区间内，反之就在 \(1\) ~ \(49\) 区间内，否者当前这个数字就是答案；
每次都能排除一半的区间，那么就知道二分法的时间复杂度就为 \(O(log n)\)。

二分法基于题目中给定的判断条件，要求该条件在搜索空间（如数组下标或可能的取值范围）中具有单调性——即存在一个分界点，使得一侧的所有元素满足条件，另一侧均不满足。通过不断缩小区间，二分法可以高效地找到满足条件部分的最后一个位置，或不满足条件部分的第一个位置。

算法模板

寻找前驱

满足条件的区间是分界点的前缀，寻找满足条件的最后一个元素，最后 \(l\) 和 \(r\) 的值相等。

while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid))
        l = mid;
    else
        r = mid - 1;
}

寻找后继

满足条件的区间是分界点的后缀，寻找满足条件的第一个元素，最后 \(l\) 和 \(r\) 的值相等。

while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid))
        r = mid;
    else
        l = mid + 1;
}

二分查找

二分查找（\(binary\) \(search\)），也称折半搜索（\(half-interval\) \(search\)），是用来在一个有序数组中查找某一元素的算法。

下面只列举寻找 \(>= x\) 和 \(<= x\) 的情况，其他情况不过多赘述。

查找 \(>= x\) 的第一个元素下标

1.手写二分

寻找后继，满足条件向后收区间。

int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r >> 1;
    if (arr[mid] >= x)
        r = mid;
    else
        l = mid + 1;
}

cout << l << endl;

2.\(lower\text{_}bound\)

使用 \(algorithm\) 库中的二分函数。

// c++20及以上
cout << ranges::lower_bound(arr, x) - arr.begin() << endl;
// c++98
cout << lower_bound(arr.begin(), arr.end(), x) - arr.begin() << endl;

查找 \(<= x\) 的最后一个元素下标

1.手写二分

寻找前驱，满足条件向前收区间。

int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (arr[mid] <= x)
        l = mid;
    else
        r = mid - 1;
}

cout << l << endl;

2.\(upper\text{_}bound\)

\(c++\) 库中没有直接寻找 \(<= x\) 的二分函数，但是有寻找 \(> x\) 的第一个元素位置的二分函数 \(upper\text{_}bound\)，通过其得到的位置减 \(1\) 就可以得到 \(<= x\) 的位置。

// c++20及以上
cout << ranges::upper_bound(arr, x) - arr.begin() - 1 << endl;
// c++98
cout << upper_bound(arr.begin(), arr.end(), x) - arr.begin() - 1 << endl;

例题

题目链接

https://www.luogu.com.cn/problem/P2249

题目描述

给你一个单调不减、长度为 \(n\) 的整数序列，然后进行 \(m\) 次查询。

每次查询一个整数 \(q\)，要求你找出 \(q\) 第一次出现的位置（位置从 \(1\) 开始计数）。

如果 \(q\) 不存在于序列中，输出 \(-1\)。
所有查询结果在同一行输出，用空格隔开。

关键代码

只列举手写二分的代码。

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    while (m--)
    {
        int x;
        cin >> x;

        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }

        a[l] == x ? printf("%d ", l) : printf("%d ", -1);
    }
}

二分答案

题目答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。判断：根据题意写个\(check\)函数，如果满足\(check\)，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

例题1

题目链接

875. 爱吃香蕉的珂珂 – 力扣（LeetCode）

题目描述

珂珂要在 \(h\) 小时内吃完 \(n\) 堆香蕉，每堆有 \(piles[i]\) 根。
她每小时以固定速度 \(k\)（整数）吃香蕉：每小时最多吃 \(k\) 根，且只能从一堆中吃；如果某堆不足 \(k\) 根，就全吃完，这小时剩下的时间也不吃别的堆。

求最小的吃香蕉速度 \(k\)，使得她能在 \(h\) 小时内吃完所有香蕉。

题目思路

显然速度 \(k\) 存在单调性，既存在一个位置 \(pos\) 使得小于 \(pos\) 的所有值都不能吃完，大于等于 \(pos\) 的所有值都可以吃完，二分 \(k\)，找后继第一个元素，由于每小时最少吃一根香蕉，那么二分下界 \(l = 1\)，每次最多吃一堆香蕉，那么二分上界就为数组最大值 \(r = max(piles)\)。

关键代码

class Solution
{
public:
    int minEatingSpeed(vector<int> &piles, int h)
    {
        int n = piles.size();

        auto check = [&](int mid) -> bool
        {
            long long cnt = 0;
            for (int i = 0; i < n; ++i)
                cnt += (piles[i] + mid - 1) / mid;

            return cnt <= h;
        };

        int l = 1, r = 1e9 + 10;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};

例题2

题目链接

410. 分割数组的最大值 – 力扣（LeetCode）

题目描述

给定一个非负整数数组 \(nums\) 和一个整数 \(k\) ，你需要将这个数组分成 \(k\) 个非空的连续子数组，使得这 \(k\) 个子数组各自和的最大值最小。

返回分割后最小的和的最大值。

题目思路

经典花匠问题，这道题目不容易想到二分，但是想到二分之后这道题就非常简单了。

可以发现在规定 \(k\) 的前提下，每个子数组各自和的最大值是满足单调性的。我们规定 \(limit\) 为所有划分出数组和的最大值，既所有子数组都必须小于等于 \(limit\)，那么这个 \(limit\) 足够大的时候必然满足条件，很小的时候肯定不满足条件，那么就可以想到这个 \(limit\) 存在一个分界点使得左侧全部不满足，右侧全部满足，那么直接二分后继，找到后继第一个点就可，上下界无过多要求，\(l = 0\)，\(r = 1e18\)即可。

关键代码

class Solution
{
public:
    int splitArray(vector<int> &nums, int k)
    {
        using ll = long long;

        int n = nums.size();

        auto check = [&](ll mid) -> bool
        {
            int cnt = 1;
            ll sum = 0;
            for (int i = 0; i < n; ++i)
            {
                if (sum + nums[i] <= mid)
                    sum += nums[i];
                else
                {
                    if (nums[i] > mid)
                        return 0;

                    if (cnt == k)
                        return 0;

                    sum = nums[i];
                    ++cnt;
                }
            }

            return 1;
        };

        ll l = 0, r = 1e18;
        while (l < r)
        {
            ll mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};

例题3

题目链接

719. 找出第 K 小的数对距离 – 力扣（LeetCode）

题目描述

数对 \((a,b)\) 由整数 \(a\) 和 \(b\) 组成，其数对距离定义为 \(a\) 和 \(b\) 的绝对差值。

给你一个整数数组 \(nums\) 和一个整数 \(k\) ，数对由 \(nums[i]\) 和 \(nums[j]\) 组成且满足 \(0 <= i < j < nums.length\) 。返回所有数对距离中第 \(k\) 小的数对距离。

题目思路

又是一道不容易想到二分的题目。

定义 \(limit\) 为数对距离，找出数对距离小于等于 \(limit\) 的数对个数：

如果个数大于等于 \(k\)，说明 \(limit\) 及后面大于 \(limit\) 的值的数对数量都大于等于 \(k\)；
如果小于 \(k\)，说明 \(limit\) 及前面小于 \(limit\) 的值的数对数量都小于 \(k\)。

此时就可以发现 \(limit\) 存在单调性，可以二分数对距离；由于数组中存在相同元素，所以下界为 \(0\)，上界显然 \(max(nums) – min(nums)\)，找出数对个数大于等于 \(k\) 的第一个数字即可。

怎么在\(check\)中快速找到小于等于 \(limit\) 的数对数量？

先对数组进行排序，在 \(check\) 中，依次遍历 \(i = 0,1,2…..,n – 1\)，对于每个 \(a[i]\)，都找到大于等于 \(a[i] – limit\) 的第一个元素和小于等于 \(a[i] + limit\) 的最后一个元素，此时这个区间中就是对于当前 \(i\) 所有满足条件的数对，对每个 \(i\) 的数对个数累加即可。

时间复杂度 \(O(n logn logn)\)。

关键代码

class Solution
{
public:
    int smallestDistancePair(vector<int> &nums, int k)
    {
        using ll = long long;

        ranges::sort(nums);

        int n = nums.size();
        int maxx = ranges::max(nums);
        int minn = ranges::min(nums);

        auto check = [&](int mid) -> bool
        {
            ll sum = 0;
            for (int i = 0; i < n; ++i)
            {
                int L = ranges::lower_bound(nums, nums[i] - mid) - nums.begin();
                int R = ranges::upper_bound(nums, nums[i] + mid) - nums.begin() - 1;

                if (L <= R)
                    sum += R - L;
            }

            sum /= 2;

            return sum >= k;
        };

        int l = 0, r = maxx - minn;
        while (l < r)
        {
            int mid = l + r >> 1;
            int t = check(mid);
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};

例题4

题目链接

2141. 同时运行 N 台电脑的最长时间 – 力扣（LeetCode）

题目描述

你有 \(n\) 台电脑和若干电池，每个电池有一定电量（单位：分钟），你需要让所有 \(n\) 台电脑同时连续运行尽可能久。

每台电脑同一时间只能用一个电池；
但你可以随时切换电池（包括换别人用过的），切换不花时间；
电池不能充电，也不能同时给多台电脑供电。

求这 \(n\) 台电脑能同时运行的最长时间。

题目思路

假设让所有电脑同时运行 \(x\) 分钟，那么所有电量大于 \(x\) 的电池只能被使用 \(x\) 分钟，所有电量小于 \(x\) 的电池可以被完全使用，那么每个电池的贡献就是 \(min(batteries[i], x)\)，那么所有的贡献就是所有电脑可以运行的时间总和 \(sum\)。

证明：2141. 同时运行 N 台电脑的最长时间 – 力扣（LeetCode）

对于运行时间 \(x\)：

如果 \(sum >= x * n\)，说明当前所有电池的贡献足以让所有电脑运行 \(x\) 分钟，那么更小的 \(x\) 也肯定是满足的。
如果 \(sum < x * n\)，说明当前所有电池的贡献不足以让所有电脑运行 \(x\) 分钟，那么更大的 \(x\) 也肯定是不满足的。

此时发现 \(x\) 存在单调性，二分前驱中最大的 \(x\)，二分下界显然为 \(0\)，上界为 \(sum(batteries) / n + 1\)。

关键代码

class Solution
{
public:
    long long maxRunTime(int n, vector<int> &batteries)
    {
        using ll = long long;

        ranges::sort(batteries);

        int m = batteries.size();

        auto check = [&](ll mid) -> bool
        {
            ll sum = 0;
            for (int i = 0; i < m; ++i)
                sum += min(1ll * batteries[i], mid);

            return sum >= mid * n;
        };

        ll tot = accumulate(batteries.begin(), batteries.end(), 0ll);
        ll l = 0, r = tot / n + 1;
        while (l < r)
        {
            ll mid = l + r + 1 >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }

        return l;
    }
};

2.https://codeforces.com/contest/2093/problem/E

3.https://codeforces.com/contest/2009/problem/E

4.https://codeforces.com/contest/2149/problem/F

5.https://codeforces.com/contest/1324/problem/D

6.2187. 完成旅途的最少时间 – 力扣（LeetCode）

7.https://www.luogu.com.cn/problem/P1873

8.https://www.luogu.com.cn/problem/P2440

9.https://www.luogu.com.cn/problem/P2678

10.https://www.luogu.com.cn/problem/P3853

11.https://www.luogu.com.cn/problem/P1182

注：一些概念性的内容会有借鉴网上其他算法大佬的文章内容，非100%原创，题目部分为左乘云大佬二分答案课上题目及思路。

概述

算法模板

寻找前驱

寻找后继

二分查找

查找 \(>= x\) 的第一个元素下标

1.手写二分

2.\(lower\text{_}bound\)

查找 \(<= x\) 的最后一个元素下标

1.手写二分

2.\(upper\text{_}bound\)

例题

题目链接

题目描述

关键代码

二分答案

例题1

题目链接

题目描述

题目思路

关键代码

例题2

题目链接

题目描述

题目思路

关键代码

例题3

题目链接

题目描述

题目思路

关键代码

例题4

题目链接

题目描述

题目思路

关键代码

题目推荐

发送评论编辑评论

概述

算法模板

寻找前驱

寻找后继

二分查找

查找 \(>= x\) 的第一个元素下标

1.手写二分

2.\(lower\text{_}bound\)

查找 \(<= x\) 的最后一个元素下标

1.手写二分

2.\(upper\text{_}bound\)

例题

题目链接

题目描述

关键代码

二分答案

例题1

题目链接

题目描述

题目思路

关键代码

例题2

题目链接

题目描述

题目思路

关键代码

例题3

题目链接

题目描述

题目思路

关键代码

例题4

题目链接

题目描述

题目思路

关键代码

题目推荐

发送评论 编辑评论

推荐文章

发送评论编辑评论