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

2019-12-15  本文已影响0人  suoga

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

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

二分查找

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

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

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

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

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

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

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

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

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

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

比如：

二分在优化中的应用

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

上一篇下一篇

猜你喜欢

热点阅读