算法题套路总结（二）——二分法

上一篇我们总结了链表题目的常见题型和套路，本章我们再来看看二分。实话实说，二分的题目通常来说都比链表题目复杂一些，经常需要一些思维，最关键的点就是看出问题的可二分性。什么叫可二分性呢，换句话说，什么样的问题是可以二分的？
这里最大的原则就是单调性原则：如果x可行，那么t (t<x)必然可行。所以，一道题能不能使用二分法，关键就是看这个题目是否符合单调性。

总体来说，二分的题目有两类：

• 二分查找
• 二分验证（二分答案）

二分查找

二分查找的代码非常简单，就是让你在一个有序队列中找到某个对象。几乎不会出现裸的二分查找题目，大部分都是基于它的一些变种，主要难点就是处理上下界的边界case。二分查找有几项是属于基本功的，大家需要非常熟练地掌握：
比如在数组 1 1 2 2 2 2 3 5 5 5 7 中：

• 找到最左边的2的下标
• 找到最右边的2的下标
• 如果要插入6，返回其下标

这里介绍一个我个人觉得比较好的二分模板(伪代码):

fn binary_search(arr: &Vec<i32>, v: i32) -> Result<usize, usize> {
  let (mut left, mut right) = (0, arr.len()-1);
  while left < right { // 是<，不是<=
    let mid = (left+right) / 2;  // 代码里尽量不要用>>1，绝大部分编译器会自动把/2变成>>1
    if arr[mid] >= v { // 关键判断，大部分库中的cmp函数
      right = mid;  // 不是mid-1
    } else {
      left = mid + 1;
    }
  }
  if arr[right] == v {
    Ok(right) 
  } else if arr[right] < v{
    Err(right+1)
  } else {
    Err(right)
  }
}

以上的二分代码框架，能够正确处理大部分的查找场景。当然，就像之前说的，如果要找最靠右的元素呢？做个小改动即可

while left < right {
  if arr[mid] > v {
    right = mid -1;
  } else {
    left = mid;
  }
}
// left

以下是一些非常基础的二分题目：

• 搜索插入位置，完完全全最基本的二分查找，可以验证你的二分代码是否正确
• 34. 在排序数组中查找元素的第一个和最后一个位置，找最左边和最右边的元素，同样是基本的二分

二分查找的一个经典应用就是单调函数求最值，比如：

• 69. x 的平方根，由于x^2在x∈[0, ∞)单调递增，我们直接进行尝试即可（所谓的二分答案）
• 33. 搜索旋转排序数组，这是一个非常经典的二分查找，它面对的是两个单调递增区间，但不是全局单调递增的。针对这道题，我们一个简单的办法是，先找出两个区间的反转点，也就是找到idx满足arr[idx-1] > arr[idx] && arr[idx] < arr[idx+1]。找到idx之后，idx之前和之后就是两个完全单调的区间，就能方便地二分查找了。由于题目保证了所有元素都不相同，因此可以发现前面区间的最小值大于后面区间的最大值。利用这个条件，当我们找到一个arr[mid]，如果它大于arr[L]，说明它处在第一个单调递增区间，此时反转点肯定在mid之后；否则它处在第二个单调递增区间，反转点在mid之前。
• 81. 搜索旋转排序数组 II，这道题和33题类似，但是因为存在重复元素，因此可能出现arr[L] == arr[R]的情况，进而使得我们无法判定arr[mid]是在哪个区间。极端情况下，整个数组所有元素都一样。因此这道题，当遇到两个端点一样时，两端点各自都向内收缩一步即可（可能会退化成O(N)），剩下只要保证端点不一致，就能够用之前的办法进行判断。
• 153. 寻找旋转排序数组中的最小值，这道题和之前题目一样，更简单了，只需要找到两个区间交界点即可。
• 154. 寻找旋转排序数组中的最小值 II，这道题就是153包含了重复元素的case，遇到处理方式和之前一样，遇到收尾元素一致时，都内收一步即可，所以极端情况下可能退化成O(n)
• 162. 寻找峰值，这道题可能有多个峰值，返回任意一个即可。经过分析可以发现，如果一个元素处于一段上升区间，那么它右侧必然会有峰值。如果它处在一段下降区间，那么它左侧必然有峰值。因此，我们可以不断地缩小范围，直到找到我们的目标。

二分查找还一类比较典型的题目是在矩阵中进行查找，比如：

• 74. 搜索二维矩阵，我们可以先通过二分定位到行，最后在该行进行二分，定位到最终答案。另一种方式是把二维转换成一维（第i行放到第i-1行之后），这时候就是一维数组的二分查找，不过此时L和R需要转换一下映射到原始的二维数组上去
• 240. 搜索二维矩阵 II，这道题没办法真正的“二分”，但是可以从左下角开始，由于每一列和每一行都是从小到大有序的，那么左下角的元素就是所在列的最大值和所在行的最小值。因此，如果target比左下角小，那么答案肯定不在左下角所在的行，否则不在左下角所在的列。这样比较一次可以排除一行或者一列。最终只剩一行或一列时，再一次二分即可找到target。整体复杂度O(n+logn)。
• 302. 包含全部黑色像素的最小矩形，这道题有些难度。由于题中保证像素点连续，且只有一个区块，因此要求面积只需要找到最左、左右、最上、最下的4个像素点即可。暴力的复杂度是O(n^2)。但是更进一步，由于题目告诉了其中一个像素点的位置(row, col)，因此，最左的点肯定不是第col列就是在它左侧。同时可以发现，由于区块是连续的，如果我们发现col左边某一列t没有黑点，就可以确定最左的点在第t列右侧，因此可以二分找到最左点。用同样的方法可以找到最右、最上、最下。

二叉搜索树（BST）大部分题目其实也是二分的思想，我们这里可以把BST相关的题目也归结为二分法，比较典型的：

• 230. 二叉搜索树中第K小的元素，这道题最简单就是通过中序遍历即可找到第k小，复杂度是O(k)。对于follow up，如果二叉树频繁更新时，每次中序遍历找第k小，复杂度就是O(n^2)。但是，如果我们在每个节点维护两个计数器，记录它的左子树所有节点个数以及右子树所有节点个数。那么当我们找第k小时，如果左子树个数大于等于k，则在左子树中找，如果左子树个数等于k-1，则答案就是当前节点，否则在右子树中找第k-weight_left-1小。这样可以把时间复杂度优化到O(nlogk)。
• 270. 最接近的二叉搜索树值，要在树中找到最接近target的节点的值，其实就是在树中找出:
  • 值大于等于target的最小的节点
  • 值小于target的最大的节点
    因此可以通过两次遍历来找出值，经过对比得出答案。

这里还有一种更巧妙的办法，考虑一下，如果当前节点比target大，那么由于BST的特性，当前节点所有右子树的值都大于target，而且比当前节点大得更多，因此结果不可能在右子树。同理，如果当前节点比target小，那么左子树比target小得更多，因此答案如果不是当前节点那么只可能在右子树。

余下大部分二分的题目基本上都是二分答案，需要多多做题来积累思路和感觉。二分答案的题目有一个很明显的特征，就是让你找出:

• 最大值最小
• 最小值最大

一般这种题目第一想法就应该是看它是否能够二分，二分的对象是否具备单调性，或者即使不具备怎么改一下构造出单调性（这种题目一般就比较难了）

比如：

• 209. 长度最小的子数组，二分答案，先看长度为m的子数组是否可行，验证可行性需要O(n)的复杂度，如果不行再加大子数组长度，否则减小长度，总复杂度O(nlogn)
• 275. H指数 II，这道题也是一个很典型的二分答案加验证的题目，只要想到二分，剩下的就简单了。并且由于数组是有序的，验证是否数组中是否有h个数大于等于h，只需要看arr[-h]是否大于等于h即可，因此总体时间复杂度是O(logN)
• 287. 寻找重复数，这是一道比较有意思的二分题目。我们二分答案w，然后去验证重复的数是否在[1, w]这个区间中。只有这样才能满足二分的单调性约束。而由于题目约定有且仅有一个数是重复的，那么我们可以扫描整个数组，每遇到一个处在[1, w]的数，我们就把计数器加一。如果没有重复，那么最终123..w每个数出现一次，计数器值为w，否则计数器值大于w。
  当然这道题还有另一种做法就是按照图来建模，把nums[i]=j理解为，节点i到节点j有一条单向边。由于有重复，那么必然存在nums[i]=t, nums[j]=t，也就是说图中存在环，且环的起点就是t。同时，由于每个点只有一条边，因此相当于单链表，所以问题转化成了单链表上寻找环的起点——我们上一章链表中的经典题目（快慢指针）

二分在优化中的应用

二分作为单独的题目，大部分并不难，只要掌握了思想，很多题都很简单。二分更常见的是和融合在复杂的题目中，作为算法的一部分，来降低整体复杂度。最常见的就是：单调队列。比如：

• 300. 最长上升子序列，这道题算是经典的DP入门题目，但是除了DP还有另一种更高效的算法，就是单调队列。由于我们要找最长上升序列，那么我们当然是希望长度为k的上升序列的最后一个数越小越好，这样后面的数才有更大的概率比它大，从而形成长度为k+1的上升序列。因此，我们利用一个单调队列来维护长度为i的序列的最后一个数能达到的最小值（可能有点绕，稍微理解下）。比如拿 [10,9,2,5,3,7,101,18]举例，一开始队列为空，然后把10入队，然后对于9，我们可以发现，长度为1的队列的最后一个数是10，9无法接在后面形成长度为2的序列。但是，它可以替换掉10，这样长度为1的序列最小值就是9了。接下来对于2亦是如此，queue = [2]。当扫描到5时，我们发现5可以接到长度为1的序列后面，因此queue= [2 5]。当扫到3时，发现长度为2的是5，不行，但是可以接到长度为1的序列后面，因此queue = [2 3]……而由于队列queue是单调的，因此在找当前值可以放到谁后面时，可以利用二分查找快速定位。因此整体复杂度可以降到O(nlogn)

• 354. 俄罗斯套娃信封问题，由于信封必须满足长和宽都大于另一个信封的长和宽才可以装，我们可以先把信封按照长度从大到小排序。排序过后，可以发现，剩下的只需要比较宽了。（长度相同的信封，可以只保留一个宽度最小的那个，这里有个技巧就是排序时如果长度相同则按宽度从大到小排序，这样可以规避掉长度相同的问题）。此时问题就变成了对于宽的最长上升序列。利用上述的优先队列，时间复杂度是nlogn，加上排序，总共2nlogn

• 352. 将数据流变为多个不相交区间，这道题可以用一个二元组(a,b)来表示从a开始长度为b的连续区间。每次插入数时，可以先假设所有区间长度都是1，然后二分查找出新插入的元素w应该插入的位置idx。定位到位置之后，其实由于arr[idx-1] = (t, len)，所以看w是否小于t+len，如果等于t+len的话，表相当于可以直接接到前面区间后面，只需要把len+1。同理，也需要看w是否可以接到下一个区间的前面。最后再看是否可以把前后两个区间串联合并成一个区间。

• 363. 矩形区域不超过 K 的最大数值和，这道题最暴力的就是 N^2 算出前缀和（sum[i][j]表示左上角(0,0)右下角(i,j)]的矩形的和），然后分别枚举左上角和右下角，计算出矩形和，找到最大的值。总体复杂度 N^4 ，太慢。回忆一下之前有道题，让你找出一维数组连续区间的最大值。如果我们先枚举第i行和第j行，把i..j行每一列所有元素累加，最后我们会得到一行，然后问题变成了一维。但是，之前的问题是求最大值，此题是求不大于k的最大值。借鉴前缀和的思路，区间和可以用sum[i]-sum[j-1]来表示，因此有sum[j]-sum[i-1] <= k，简单变形一下得到sum[j]-k <= sum[i-1]，也就是在sum[j]之前找到一个最大的小于等于sum[j]-k的数。这里是个常见优化方式，就是维护一颗支持查找lowerbound的BST，然后可以用logN的时间求出值。因此，整体时间复杂度可以降低到N^3logN。题目的follow up中问，如果行数远大于列数怎么办？上面，的复杂度分析，我们默认行数和列数相等。如果用N表示行，M表示列，枚举行N^2，列MlogM，因此总体复杂度是N*N*M*LogM。而由于N远大于M，因此可以把枚举顺序交换，把先M^2枚举列，然后按行压缩，最终复杂度是M*M*N*logN。因为N远大于M，因此M*LogN<N*LogM。这种基于二分的常见优化应用非常广泛，需要深刻理解。