Loading... Leetcode前700题有关二分分类源于：https://leetcode.cn/circle/article/48kq9d/ <img src="https://pic-1256393142.cos.ap-nanjing.myqcloud.com/image-20221206103238338.png" alt="image-20221206103238338" style="zoom:67%;" style=""> ## 基本理论 二分即在定义边界后，根据条件不断收缩边界，最终找到最先或者最后符合条件的那个值。主要容易出现问题每次边界变化较之前不变，导致死循环。太多理论介绍可能也无法表述清晰，直接上模板，二分模板主要有两套： **模板一：** ```java // 区间[l, r]被划分成 [l, mid] 和 [mid+1, r]时使用 int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check[mid]) // check() 判断 mid是否满足性质 r = mid; else l = mid + 1; } return l; } ``` 值得注意的地方这里 l + r >> 1，是对两个边界和取中间部分，但是**这种写法是有可能偏向于左边的（有可能正好中间），既然偏向左边，左边再没变化那么就出现了死循环。所以在这一套模板中l必须得在if判断中发生变化，否则很容易死循环。**此外我们可以想象一个数轴，中间取值为mid，当符合check函数后mid有可能是答案也有可能最终结果的在前边，所以收缩了r边界。那么重复几次这样流程，r不断向前找，可以将这个模板理解为**找到符合check的第一个数**。（可以以一个从小到大数组中，找到第一个大于target的数当做例子） **模板二：** ```java // 区间[l, r]被划分成 [l, mid-1] 和 [mid, r]时使用 int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 2; // 注意 if (check[mid]) // check() 判断 mid是否满足性质 l = mid; else r = mid - 1; } return l; } ``` 值得注意的地方这里 l + r + 1>> 1，是对两个边界和取中间部分，但是**这种写法是有可能偏向于右边的（有可能正好中间），既然偏向右边，右边再没变化那么就出现了死循环。所以在这一套模板中r必须得在if判断中发生变化，否则很容易死循环。**此外我们可以想象一个数轴，中间取值为mid，当符合check函数后mid有可能就是答案也有可能符合最终结果的在后边，所以收缩了l边界。那么重复几次这样流程，l不断向后找，可以将这个模板理解为找到**符合check的最后一个数**。（可以以一个从小到大数组中，找到最后一个小于target的数当做例子） 在我看来有了模板二分核心在于如何写check函数，下面的划分主要以不同的check为主。 ## 题目分类 ### 基本check（大小判断，且所给数据抽象角度可看为有序） 值的注意的是二分后要再次判断值是否符合结果，符合结果才可以返回，不符合根据题目需要做进一步判断（即不存在或者超出范围等情况） [374. 猜数字大小](https://leetcode.cn/problems/guess-number-higher-or-lower/)：在1-n中找到符合target的值。（注意比较关系，和模板略微有差距） [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)：找到第一个大于等于目标值的索引。（注意l+r越界，上述两种形式可以改为l + ((r - l) >> 1), l + ((r-l + 1) >> 1)） [278. 第一个错误的版本](https://leetcode.cn/problems/first-bad-version/):check函数已经给出，看成找到第一个大于等于（为true）的索引。 [367. 有效的完全平方数](https://leetcode.cn/problems/valid-perfect-square/)：在1-n（n/2）中找到第一个平方和大于等于目标值的数。 [69. x 的平方根 ](https://leetcode.cn/problems/sqrtx/):找到最后一个平方小于等于x的数。 [441. 排列硬币](https://leetcode.cn/problems/arranging-coins/)：等差数列求和后最后一个求和小于等于目标硬币数量。 [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/) 两次二分，上面两个模板分别用一遍。 **我认为上述题目均可看为模板题，而且check函数很好分析，根据具体需要做相应变化即可。** ### 特殊check（表现为数组不是顺序排列等） 这种check函数不如上述题目那么直接，通常有位置、极值等线索来作为check条件。 [540. 有序数组中的单一元素](https://leetcode.cn/problems/single-element-in-a-sorted-array/)：以索引作为check条件，起始索引为1的情况下，在没有单一元素情况下奇数索引后一个值应该和其相等。偶数的和前面的相等。由于前面出现单一元素破坏了这个条件：（真实代码编写奇数偶数关系反过来，这里以1为开始） 在奇数索引：和后面值相等，那么当前的和后面的之前均没有答案。如果不等当前值或者当前值之前有可能是答案。 在偶数索引：和前面值相等那么答案在该值之后，不等的话答案有可能是当前值或者当前值之前。 [275. H 指数 II](https://leetcode.cn/problems/h-index-ii/)：做题时候比较难受一题，主要是这个指标我个人很难理解。主要摆正一个思想返回的不是数组的值而是mid后面的个数（大于某个引用的论文个数）。转化为check语言即找到第一个大于某个引用数量论文大于等于这些论文引用的最小值。我觉得这样理解会好一点。 [436. 寻找右区间](https://leetcode.cn/problems/find-right-interval/)：本题其实更多我觉得是考察语法，学会用lamda表达式排序，排完序就是简单的二分查找。 [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/)：<font color='red'>我认为是个非常好的题目，包含了贪心的思想，又有dp的味道。我觉得本题重点不在二分查找部分。基于末尾数字越小可能构成子序列长度越长，构造一个数组每一位置值表示以该值为结尾和前面值构成的最长子序列。当然最终构造的数组不可能包含全部的值，包含的时能够构成x长度的末尾最小的子序列。所以基于此每次末尾值大于构造末尾值直接添加，否则在前面找个合适的位置赋值（位置用二分查找）。</font> [354. 俄罗斯套娃信封问题](https://leetcode.cn/problems/russian-doll-envelopes/)：<font color='red'>仍然是dp+二分查找的题目。和上一题比本题是二维形式，想办法取消一个维度的影响，自然想到排序。按照第一维升序，第二维降序。只考虑第二维，题目简化为上述题目。（因为第二维度降序不存在第一维相等情况下组成一个子序列情况）。</font> [658. 找到 K 个最接近的元素](https://leetcode.cn/problems/find-k-closest-elements/)：先找到最接近x的元素位置，然后以该元素为中心扩散即可。 [162. 寻找峰值](https://leetcode.cn/problems/find-peak-element/)：基于事实，某个值两边存在大于其的一个数，那个这边一定有峰值。 [153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/)：旋转数组，旋转前排序好状态，重点在于和数组r边界值比较判断当前在旋转数组前半段还是后半段，不断缩小r边界找到第一个小于等于r边界的值即为起点。 [154. 寻找旋转排序数组中的最小值 II](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/)：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/solution/xiang-deng-de-shi-hou-dan-du-tao-lun-by-hc428/ 上述为我对该题题解，我觉得相等地方做一个特殊判断即可，本质上和上述类似。 [33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/)：我认为这题是上面类型再升级，不仅旋转还要找值。核心还是在上面理解基础上确定目标值是在趋势上还是不在趋势上。（趋势就是mid-r或者l-mid是不是递增的） [81. 搜索旋转排序数组 II](https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/)：同样是包含重复元素，特殊地方单独判断就好。 [74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix/)：掌握一维和二维之间换算关系，本质变成二分查找模板题。 [378. 有序矩阵中第 K 小的元素](https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/)：上述分类把该题分为二份答案法，我觉得本题特点在于边界不是以索引界定，而是以最大值最小值作为边界，每次找到第一个大于等于矩阵的值数量为k的那个数（注意在这个有序矩阵找小于mid数量方法），这个值是一定存在的即为第K大的数。**范围取自矩阵最大值最小值，而mid不一定来在于矩阵。** [668. 乘法表中第k小的数](https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/)：本以为困难题用上面的思路无法通过，没想到通过了。这个矩阵比上面更特殊一些。 最后修改：2023 年 03 月 06 日 © 允许规范转载 赞 7 如果觉得我的文章对你有用，请随意赞赏