您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

面试必考的「二分算法」系统梳理

时间:2021-02-26 10:34:31  来源:  作者:

「二分」有关,算是非常普遍与重要的知识点。然而有很多同学依然没能很好地掌握,总是会在各种细节上跌跟头,因此今天我们将对二分算法进行系统地梳理。

「二分」一共有三类常见应用,分别是「整数二分」、「实数二分」以及「二分答案」,接下来将分别介绍这三类应用的具体形式。

一、整数二分

整数二分即为在整数集合上的二分,常见的用法有:在单调序列中查找「某个数是否出现过」、「某个数最早出现的位置」以及「>= 某个数中最小的数」等。

解决这类问题的思想非常统一,即对坐标区间不断进行折半,以此在 O(log(n)) 的时间复杂度内确定答案,但其「实现方法」却非常多样,由此导致很多同学在此类问题上出错。

因此接下来将通过一个例题来介绍「记录 ans」的二分实现方法,该方法较易理解且不易出错。

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

题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置,如果数组中不存在目标值 target,返回 [-1, -1]。设计并实现时间复杂度为 O(log(n)) 的算法解决此问题。

示例 1

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3

输入:nums = [], target = 0
输出:[-1,-1]

提示

  • 0 <= nums.length <= 1e5
  • -1e9 <= nums[i] <= 1e9
  • nums 是一个非递减数组
  • -1e9 <= target <= 1e9

 

题目讲解

我们以数组 nums = [3 4 4 4 6], target = 4 进行举例,首先是确定 4 的开始位置,具体代码如下:

int l = 0, r = 4, ans = 0;
while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] >= target) {
        ans = mid;
        r = mid - 1;
    }
    else l = mid + 1;
}
if (nums[ans] != target) ans = -1;

上述代码在二分过程中,[l, r] 始终代表二分搜索的区间,而 ans 则代表「数组中第一个 >= target」的位置。最后再通过判断 nums[ans] 是否等于 target 来确定 target 是否存在于数组中。

我们来模拟一下这个过程,首先二分搜索区间为 [0, 4],因此 mid = 2。此时 nums[2] >= 4,即 2 可能是「数组中第一个 >= target」的位置,因此更新 ans 为 2。

面试必考的「二分算法」系统梳理

 

又因为 nums[mid] >= 4,即答案一定不在右半区间,即 [3, 4],于是令 r = mid - 1,搜索区间变为 [0, 1]。此时 mid = 0,nums[0] < target,因此 mid 无法更新 ans。

面试必考的「二分算法」系统梳理

 

由于 nums[mid] < target,因此答案一定不在左半区间,于是 l = mid + 1,搜索区间变为 [1, 1]。此时 mid = 1,nums[1] >= target,更新 ans = 1。

面试必考的「二分算法」系统梳理

 

由于 nums[mid] >= target,于是 r = mid - 1,不再满足 l <= r 的条件,二分过程结束。最终 ans = 1,二分成功。

通过上述这个过程,我们可以总结出「整数二分」的实现规律,首先由 while (l <= r) 来控制二分进程,每次计算 mid = (l + r) / 2,并判断 mid 是否为可能的答案。如果是,则更新 ans,否则不更新。另外根据 mid 判断接下来是搜索左半区间 [l, mid - 1],还是右半区间 [mid + 1, r],不断循环。退出循环后,ans 即为要求的答案。

根据上述示例,大家可以自行完成「查找 target 结束位置」的代码,并查看下述完整代码进行验证。

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

二、实数二分

实数二分即为实数域上的二分,即二分搜索区间 [l, r] 从整数变为了实数。对比整数二分,实数二分的算法思想没有变化,唯一变化的只有二分实现方法。

通常来说实数二分有两种实现方法,第一种是通过确定好的精度 eps(如 1e-6、1e-8 等),以 l + eps < r 为循环条件,每次根据在 mid 上的判定,选择左半区间 [l, mid] 或右半区间 [mid, r]。循环结束后,l 即为最终答案,代码示例如下:

while (l + 1e-6 < r) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

有时精度不容易确定,因此直接固定循环次数进行二分,即第二种方法。与第一种方法仅有「循环条件」的区别,代码示例如下:

for (int i = 0; i < 100; i++) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

三、二分答案

二分算法成立的关键在于单调性,因此任何具有单调性的问题,我们都可以考虑在其上使用二分算法的可能性。正是基于这一点,当问题的答案具有单调性时,我们可以通过二分将「问题的求解」转化为「问题的判定」,该方法即为「二分答案」。

接下来我们将通过两道例题进一步地讲解该算法。

287. 寻找重复数

题目描述

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数,请找出这个重复的数,并只使用 O(1) 的额外空间。

 

示例 1

输入:nums = [1,3,4,2,2]
输出:2

示例 2

输入:nums = [3,1,3,4,2]
输出:3

示例 3

输入:nums = [1,1]
输出:1

示例 4

输入:nums = [1,1,2]
输出:1

提示

  • 2 <= n <= 3e4
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中只有一个整数出现两次或多次,其余整数均只出现一次

题目讲解

本题有很多种做法,但我们主要以该题为例来讲解「二分答案」,因此我们直接进入「二分答案」的思考过程。

一道题想要使用「二分答案」,其最大的前提是「答案有单调性」,而本题所求解的答案是显然的,即「重复数的值」。所以我们需要找到一个「判定条件」,使得对于二分区间 [l, r],我们可以根据其中值 mid 是否满足「判定条件」,来确定下一个搜索区间是左半部分还是右半部分。

在本题中,我们令 f(x) 表示数组中 <= x 的个数,则不难发现 f(x) 是关于 x 的单调函数,即随着 x 的变大,f(x) 要么变大要么不变。

具体来说,假设重复数为 A,则对于所有小于 A 的数 x,f(x) = x;而所有大于等于 A 的数 y,f(y) > y。例如对于数组 [1 2 2 2 3],n = 4,f(1) = 1,f(2) = 4,f(3) = 5,f(4) = 5。

由此我们可以通过「二分答案」来解决本题,对于二分区间 [l, r],其中值为 mid,若 f(mid) > mid,则说明重复数小于等于 mid,因此更新 ans = mid,且将二分区间变为 [l, mid - 1];否则不更新 ans 且二分区间变为 [mid + 1, r]。

二分答案的时间复杂度为 O(log(n)),对于特定的 mid,求解 f(mid) 的时间复杂度为 O(n),因此本题总的时间复杂度为 O(nlog(n)),具体代码如下所示:

class Solution {
public:
    bool check(vector<int>& nums, int mid) {
        int cnt = 0;
        for (int x:nums) {
            if (x <= mid) cnt++;
        }
        if (cnt > mid) return 1;
        else return 0;
    }
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size(), ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(nums, mid)) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }
};

其中 while 循环中的 check 函数即为「二分答案」问题中的「判定条件」。对于「二分答案」所适用的题目,我们通常只需对 check 函数进行修改,while 循环中的部分基本不变。

 

410. 分割数组的最大值

题目描述

给定一个非负整数数组 nums 和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 1

输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

示例 2

输入:nums = [1,2,3,4,5], m = 2
输出:9

示例 3

输入:nums = [1,4,4], m = 3
输出:4

提示

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1e6
  • 1 <= m <= min(50, nums.length)

题目讲解

查看题干,「最大值最小」,这是答案具有单调性,可用二分将「问题求解」转换为「问题判定」最常见、最典型的特征之一。

具体来说,在本题中,若「子数组和的最大值小于等于 x」符合数组分割要求,则比 x 更大的答案也一定符合要求。即当 x 为负数时,数组分割要求无法满足,但随着 x 的不断变大,会有一个分界点 A,当 x 大于等于 A 时,数组分割要求即可满足,而这个 A 即为本题答案。

由此本题从「求解 A」转换为了「二分 A 并判断数组分割要求是否可以满足」。对于二分区间 [l, r],其中值为 mid,若 mid 满足数组分割要求,则更新 ans = mid,二分区间变为 [l, mid - 1];否则不更新 ans 且二分区间变为 [mid + 1, r]。

所以本题的「判定条件」为:对于特定的 mid,判断当子数组和的最大值 <= mid 时,子数组是否可以分成 m 个非空的连续子数组。

对于该「判定条件」,我们可以使用贪心算法,从前往后遍历数组,用 sum 表示当前分割子数组的和,cnt 表示已经分割出的子数组的数量。若 sum 加上当前值 nums[i] 大于 x,则将 cnt 加 1,并将当前值作为新的一段分割子数组的开头,即 sum = nums[i]。遍历结束后,若 cnt <= m,则判定条件可以满足,否则无法满足。

由此本题得以解决,具体代码如下所示:

class Solution {
public:
    bool check(vector<int>& nums, int m, int mid) {
        int len = nums.size(), sum = 0, cnt = 1;
        for (int x:nums) {
            if (x > mid) return 0;
            if (sum + x <= mid) sum += x;
            else sum = x, cnt++;
        }
        return cnt <= m;
    }
    int splitArray(vector<int>& nums, int m) {
        int l = 0, r = 1e9, ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(nums, m, mid)) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }
};

总结一下,当问题的答案具有单调性时,我们可以通过「二分答案」将「问题的求解」转换为「问题的判定」,进而完成解题的过程。

四、综合练习

最后我们以一道经典二分题为例进行综合练习,该题目难度较大,也是一道经典的面试题,希望大家能好好理解并掌握。

4. 寻找两个正序数组的中位数

题目描述

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数,且时间复杂度不高于 O(log (m+n))。

示例 1

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

示例 4

输入:nums1 = [], nums2 = [1]
输出:1.00000

示例 5

输入:nums1 = [2], nums2 = []
输出:2.00000

提示

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -1e6 <= nums1[i], nums2[i] <= 1e6

题目讲解

首先考虑一下本题能否「二分答案」,由于奇数长度与偶数长度解法类似,因此仅考虑 m + n 为奇数时的情况。

当 m + n 为奇数时,中位数即为两个数组排序后第 (m + n + 1) / 2 个数,因此令 f(x) 表示两个数组中 <= x 的数的个数,中位数即为满足 f(x) >= (m + n + 1) / 2 中最小的 x。由于两个数组均为正序,因此对于一个特定的 x,我们可以通过两次二分在 O(log(n) + log(m)) 的时间复杂度内求得 f(x)。

由此我们可以得知「二分答案」的时间复杂度为 O(log(2e6)(log(n)+log(m))),其中 2e6 为「二分答案」初始区间 [-1e6, 1e6] 的长度。因此「二分答案」无法达到「时间复杂度不高于 O(log (m+n))」的要求,我们需要转换思路。

重新思考中位数的作用,我们可以发现:中位数常用于将一个序列划分为长度最多相差 1 的两部分,且其中一部分的元素始终大于等于另一部分。

为了便于表述,将 nums1 和 nums2 数组分别记为 A 和 B。接下来模拟序列的划分过程,在 A 数组中选取前 i 个数(A[0], A[1], ..., A[i-1]),在 B 数组中选取前 j 个数(B[0], B[1], ..., B[j-1])。这 i + j 个数组成第一部分,剩下的 n + m - i - j 个数为第二部分。

进一步地,当 m + n 为偶数时,两部分长度一致,且第一部分最大值小于等于第二部分最小值,即:

面试必考的「二分算法」系统梳理

 

此时中位数等于

面试必考的「二分算法」系统梳理

 

;当 m + n 为奇数时,我们规定第一部分长度比第二部分大 1,且两部分的最值关系依然满足,即:

面试必考的「二分算法」系统梳理

 


此时中位数等于

面试必考的「二分算法」系统梳理

 

。观察上述两个式子,发现无论 m + n 为奇还是偶,均满足

面试必考的「二分算法」系统梳理

 

。因此为了便于计算,我们将

面试必考的「二分算法」系统梳理

 

面试必考的「二分算法」系统梳理

 

统一为

面试必考的「二分算法」系统梳理

 

(此处为整除)。

又因为 A、B 均为升序数组,因此上述两个式子可以修改为:

面试必考的「二分算法」系统梳理

 

继续观察可以发现,当 i 增大时,j 在减小,即随着 i 的增加,A[i-1] 不断增加,而 B[j] 则不断减小。因此一定存在一个临界点 (i, j) 满足 A[i-1] ≤ B[j] ,而 i 再增加 1 则不再满足,即:

面试必考的「二分算法」系统梳理

 

不难发现,临界点 (i, j) 刚好满足 i、j 划分数组的要求,因此本题可以通过二分 i 的位置,寻找最大的满足 A[i-1] ≤ B[j] 的 i,即可完成数组划分并求得中位数。

另外需要注意 i、j 可能会超出数组范围,因此规定 A[-1] = B[-1] = -1e9,A[m] = B[n] = 1e9。由此本题得以解决,时间复杂度为 O(log(min(m, n))),满足题目要求。

代码实现

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) swap(nums1, nums2);
        int n = nums1.size(), m = nums2.size(), l = 0, r = n, ans = 0;
        while (l <= r) {
            int i = (l + r) / 2, j = (n + m + 1) / 2 - i;
            if (i <= 0 || j >= m || nums1[i-1] <= nums2[j]) {
                ans = i;
                l = i + 1;
            }
            else r = i - 1;
        }
        int i = ans, j = (n + m + 1) / 2 - i, x1 = -1e9, x2 = -1e9, x3 = 1e9, x4 = 1e9;
        if (i > 0) x1 = nums1[i-1];
        if (j > 0) x2 = nums2[j-1];
        if (i < n) x3 = nums1[i];
        if (j < m) x4 = nums2[j];
        if ((n + m) % 2) return max(x1, x2);
        else return (max(x1, x2) + min(x3, x4)) / 2.0;
    }
};

总结

二分是一个非常常见却又极其精妙的算法,经常成为解题的一个突破口。该算法一共有三类常见应用,即「整数二分」、「实数二分」以及「二分答案」,其中「二分答案」能将「问题的求解」转换为「问题的判定」,因此应用非常广泛。

二分并没有固定的模板与套路,灵活性非常高,因此我们需要深刻理解其算法思想,并加以习题来巩固,以期早日掌握。

 

本文作者:Gene_Liu

声明:本文归 “力扣” 版权所有,如需转载请联系。文中部分图片来源于网络,如有侵权联系删除。



Tags:二分算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
「二分」有关,算是非常普遍与重要的知识点。然而有很多同学依然没能很好地掌握,总是会在各种细节上跌跟头,因此今天我们将对二分算法进行系统地梳理。「二分」一共有三类常见应...【详细内容】
2021-02-26  Tags: 二分算法  点击:(169)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条