前言

大家好，我是 lucifer。明天给大家带来的是《二分》专题。先高低本文的提纲，这个是我用 mindmap 画的一个脑图，之后我会持续欠缺，将其余专题逐步完善起来。

大家也能够应用 vscode blink-mind 关上源文件查看，外面有一些笔记能够点开查看。源文件能够去我的公众号《力扣加加》回复脑图获取，当前脑图也会继续更新更多内容。vscode 插件地址：https://marketplace.visualstu...

本系列蕴含以下专题：

  • 简直刷完了力扣所有的链表题，我发现了这些货色。。。
  • 简直刷完了力扣所有的树题，我发现了这些货色。。。
  • 简直刷完了力扣所有的堆题，我发现了这些货色。。。（上）
  • 简直刷完了力扣所有的堆题，我发现了这些货色。。。（下）
  • 简直刷完了力扣所有的二分题，我发现了这些货色。。。（上）

<!-- more -->

本专题预计分两局部两进行。上一节次要讲述基本概念 和 一个核心。这一节咱们持续学习两种二分类型 和四大利用。没有看过上篇的倡议先看一下上篇，地址在下面。

如果感觉文章有用，请点赞留言转发一下，让我有能源持续做上来。

上篇回顾

上篇次要就是带大家理解几个概念，这些概念对做题极为重要，请务必把握。接下来解说了二分法的核心 - 折半，这个核心须要大家做任何二分都要放到脑子中。

二分法的精华正如开篇提到的二分法是一种让未知世界无机可乘的算法。二分法无论如何咱们都能够舍弃一半解，也就是无论如何都能够将解空间砍半。难点就是下面提到的两点：什么条件 和 舍弃哪局部。

接下来，咱们持续下篇。下篇注次要内容是两种类型和四大利用。

其中两种类型次要解决的的是：这道题我的解空间以及明确进去了，如何用代码找出具体的值。而四大利用次要解决的是：如何结构解空间（更多的状况则是如何构建有序序列）以及一些变体。

这两局部都是实操性很强的内容。这里我揭示大家，在了解这两局部内容的同时，请大家务必牢记一个核心折半。

两种类型

问题定义

这里的问题定义是一个广义的问题。而如果你了解了这个问题之后，能够将这个具体的问题进行推广以适应更简单的问题。对于推广，咱们之后再谈。

给定一个由数字组成的有序数组 nums，并给你一个数字 target。问 nums 中是否存在 target。如果存在， 则返回其在 nums 中的索引。如果不存在，则返回 - 1。

这是二分查找中最简略的一种模式。当然二分查找也有很多的变形，这也是二分查找容易出错，难以把握的起因。

常见变体有：

  • 如果存在多个满足条件的元素，返回最右边满足条件的索引。
  • 如果存在多个满足条件的元素，返回最左边满足条件的索引。
  • 数组不是整体有序的。 比方先升序再降序，或者先降序再升序。
  • 将一维数组变成二维数组。
  • 。。。

接下来，咱们一一进行查看。

前提

  • 数组是有序的（如果无序，咱们也能够思考排序，不过要留神排序的复杂度）
这个有序的数组可能是题目间接给的，也可能是你本人结构的。比方求数组的逆序数就能够在本人结构的有序序列上做二分。

术语

为了前面形容问题不便，有必要引入一些约定和术语。

二分查找中应用的术语：

  • target —— 要查找的值
  • index —— 以后地位
  • l 和 r —— 左右指针
  • mid —— 左右指针的中点，用来确定咱们应该向左查找还是向右查找的索引（其实就是膨胀解空间）

值得注意的是，除了 target 是固定不变的，其余都是动态变化的。其中 l 和 r 指的是解空间的上下界，mid 是上下界的两头值， index 是遍历指针，用于管制遍历过程。

查找一个数

后面咱们曾经对问题进行了定义。接下来，咱们须要对定义的问题进行剖析和求解。

为了更好了解接下来的内容，咱们解决最简略的类型 - 查找某一个具体值 。

算法形容：

  • 先从数组的两头元素开始，如果两头元素正好是要查找的元素，则搜寻过程完结；
  • 如果指标元素大于两头元素，那么数组中小于两头元素的值都能够排除（因为数组有序，那么相当于是能够排除数组左侧的所有值），解空间能够膨胀为 [mid+1, r]。
  • 如果指标元素小于两头元素，那么数组中大于两头元素的值都能够排除（因为数组有序，那么相当于是能够排除数组右侧的所有值），解空间能够膨胀为 [l, mid - 1]。
  • 如果在某一步骤解空间为空，则代表找不到。

举一个具体的例子不便大家减少代入感。假如 nums 为 [1,3,4,6,7,8,10,13,14]， target 为 4·。

  • 刚开始数组两头的元素为 7
  • 7 > 4 ，因为 7 左边的数字都大于 7 ，因而不可能是答案。咱们将范畴缩写到了 7 的左侧。

  • 解空间变成了 [1,3,4,6]，此时两头元素为 3。
  • 3 < 4，因为 3 右边的数字都小于 3 ，因而不可能是答案。咱们将范畴缩写到了 3 的右侧。

  • 解空间变成了 [4,6]，此时两头元素为 4，正好是咱们要找的，返回其索引 2 即可。

复杂度剖析

因为这种搜索算法每一次比拟都使搜寻范畴放大一半，是典型的二分查找。

  • 均匀工夫复杂度： $O(logN)$
  • 最坏工夫复杂度： $O(logN)$

  • 空间复杂度

    • 迭代: $O(1)$
    • 递归： $O(logN)$（无尾调用打消）
前面的复杂度也是相似的，不再赘述。

思维框架

如何将下面的算法转换为容易了解的可执行代码呢？

大家不要小看这样的一个算法。就算是这样一个简简单单，朴实无华的二分查找， 不同的人写进去的差异也是很大的。 如果没有一个思维框架领导你，不同的工夫你可能会写出差别很大的代码。这样的话，犯错的几率会大大增加。这里给大家介绍一个我常常应用的思维框架和代码模板。

首先定义解空间为 [left, right]，留神是左右都闭合，之后会用到这个点

你能够定义别的解空间模式，不过前面的代码也相应要调整，感兴趣的能够试试别的解空间。
  • 因为定义的解空间为 [left, right]，因而当 left <= right 的时候，解空间都不为空，此时咱们都须要持续搜寻。 也就是说终止搜寻条件应该为 left <= right。
举个例子容易明确一点。 比方对于区间 [4,4]，其蕴含了一个元素 4，因而解空间不为空，须要持续搜寻（试想 4 恰好是咱们要找的 target，如果不持续搜寻， 会错过正确答案）。而当解空间为 [left, right) 的时候，同样对于 [4,4]，这个时候解空间却是空的，因为这样的一个区间不存在任何数字·。

  • 循环体内，咱们一直计算 mid ，并将 nums[mid] 与 目标值比对。

    • 如果 nums[mid] 等于目标值， 则提前返回 mid（只须要找到一个满足条件的即可）
    • 如果 nums[mid] 小于目标值， 阐明目标值在 mid 右侧，这个时候解空间可放大为 [mid + 1, right] （mid 以及 mid 左侧的数字被咱们排除在外）
    • 如果 nums[mid] 大于目标值， 阐明目标值在 mid 左侧，这个时候解空间可放大为 [left, mid - 1] （mid 以及 mid 右侧的数字被咱们排除在外）
  • 循环完结都没有找到，则阐明找不到，返回 -1 示意未找到。

代码模板

Java
public int binarySearch(int[] nums, int target) {    // 左右都闭合的区间 [l, r]    int left = 0;    int right = nums.length - 1;    while(left <= right) {        int mid = left + (right - left) / 2;        if(nums[mid] == target)            return mid;        if (nums[mid] < target)                  // 解空间变为 [mid+1, right]            left = mid + 1;        if (nums[mid] > target)            // 解空间变为 [left, mid - 1]            right = mid - 1;    }    return -1;}
Python
def binarySearch(nums, target):    # 左右都闭合的区间 [l, r]    l, r = 0, len(nums) - 1    while l <= r:        mid = (left + right) >> 1        if nums[mid] == target: return mid        # 解空间变为 [mid+1, right]        if nums[mid] < target: l = mid + 1        # 解空间变为 [left, mid - 1]        if nums[mid] > target: r = mid - 1    return -1
JavaScript
function binarySearch(nums, target) {  let left = 0;  let right = nums.length - 1;  while (left <= right) {    const mid = Math.floor(left + (right - left) / 2);    if (nums[mid] == target) return mid;    if (nums[mid] < target)      // 解空间变为 [mid+1, right]      left = mid + 1;    if (nums[mid] > target)      // 解空间变为 [left, mid - 1]      right = mid - 1;  }  return -1;}
C++
int binarySearch(vector<int>& nums, int target){  if(nums.size() == 0)    return -1;  int left = 0, right = nums.size() - 1;  while(left <= right){    int mid = left + ((right - left) >> 1);    if(nums[mid] == target){ return mid; }    // 解空间变为 [mid+1, right]    else if(nums[mid] < target)    left = mid + 1;    // 解空间变为 [left, mid - 1]    else    right = mid - 1;  }  return -1;}

寻找最左插入地位

下面咱们讲了寻找满足条件的值。如果找不到，就返回 -1。那如果不是返回 -1，而是返回应该插入的地位，使得插入之后列表依然有序呢？

比方一个数组 nums: [1,3,4]，target 是 2。咱们应该将其插入（留神不是真的插入）的地位是索引 1 的地位，即 [1,2,3,4]。因而寻找最左插入地位应该返回 1，而寻找满足条件的地位 应该返回-1。

另外如果有多个满足条件的值，咱们返回最左侧的。 比方一个数组 nums: [1,2,2,2,3,4]，target 是 2，咱们应该插入的地位是 1。

思维框架

具体算法：

  • 首先定义解空间为 [left, right]，留神是左右都闭合，之后会用到这个点。
你能够定义别的解空间模式，不过前面的代码也相应要调整，感兴趣的能够试试别的解空间。
  • 因为咱们定义的解空间为 [left, right]，因而当 left <= right 的时候，解空间都不为空。 也就是说咱们的终止搜寻条件为 left <= right。
  • 当 A[mid] >= x，阐明找到一个备胎，咱们令 r = mid - 1 将 mid 从解空间排除，持续看看有没有更好的备胎。
  • 当 A[mid] < x，阐明 mid 基本就不是答案，间接更新 l = mid + 1，从而将 mid 从解空间排除。
  • 最初解空间的 l 就是最好的备胎，备胎转正。

代码模板

Python
def bisect_left(nums, x):    # 内置 api    bisect.bisect_left(nums, x)    # 手写    l, r = 0, len(A) - 1    while l <= r:        mid = (l + r) // 2        if A[mid] >= x: r = mid - 1        else: l = mid + 1    return l

寻找最右插入地位

思维框架

具体算法：

  • 首先定义解空间为 [left, right]，留神是左右都闭合，之后会用到这个点。
你能够定义别的解空间模式，不过前面的代码也相应要调整，感兴趣的能够试试别的解空间。
  • 因为咱们定义的解空间为 [left, right]，因而当 left <= right 的时候，解空间都不为空。 也就是说咱们的终止搜寻条件为 left <= right。
  • 当 A[mid] > x，阐明找到一个备胎，咱们令 r = mid - 1 将 mid 从解空间排除，持续看看有没有更好的备胎。
  • 当 A[mid] <= x，阐明 mid 基本就不是答案，间接更新 l = mid + 1，从而将 mid 从解空间排除。
  • 最初解空间的 l 就是最好的备胎，备胎转正。

代码模板

Python
def bisect_right(nums, x):    # 内置 api    bisect.bisect_right(nums, x)    # 手写    l, r = 0, len(A) - 1    while l <= r:        mid = (l + r) // 2        if A[mid] <= x: l = mid + 1        else: r = mid - 1    return l

以上就是两种二分的根本模式了。而在理论的写代码过程中，我不会应用寻找满足条件的值模板，而是间接应用最左 或者 最右 插入模板。为什么呢？因为后者蕴含了前者，并还有前者实现不了的性能。比方我要实现寻找满足条件的值，就可间接应用最左插入模板找到插入索引 i，只不过最初判断一下 nums[i] 是否等于 target 即可，如果不等于则返回 -1，否则返回 i。这也是为什么我将二分分为两种类型，而不是三种甚至四种的起因。

另外最左插入和最右插入能够联合应用从而求出有序序列中和 target 相等的数的个数，这在有些时候会是一个考点。代码示意：

nums = [1,2,2,2,3,4]i = bisect.bisect_left(nums, 2) # get 1j = bisect.bisect_right(nums, 2) # get 4# j - i 就是 nums 中 2 的个数

为了形容不便，当前所有的最左插入二分我都会简称最左二分，代码上间接用 bisect.bisect_left 示意，而最右插入二分我都会简称最右二分，代码上用 bisect.bisect_right 或者 bisect.bisect 示意。

小结

对于二分题目首先要明确解空间，而后依据肯定条件（通常是和两头值比拟），舍弃其中一半的解。大家能够先从查找满足条件的值的二分动手，进而学习最左和最右二分。同时大家只须要把握最左和最右二分即可，因为后者性能大于前者。

对于最左和最右二分，简略用两句话总结一下：

  1. 最左二分一直膨胀右边界，最终返回左边界
  2. 最右二分一直膨胀左边界，最终返回右边界

四大利用

基础知识铺垫了差不多了。接下来，咱们开始干货技巧。

接下来要讲的：

  • 能力检测和计数二分实质差不多，都是一般二分 的泛化。
  • 前缀和二分和插入排序二分，实质都是在构建有序序列。

那让咱们开始吧。

能力检测二分

能力检测二分个别是：定义函数 possible， 参数是 mid，返回值是布尔值。外层依据返回值调整"解空间"。

示例代码（以最左二分为例）：

def ability_test_bs(nums):  def possible(mid):    pass  l, r = 0, len(A) - 1  while l <= r:      mid = (l + r) // 2      # 只有这里和最左二分不一样      if possible(mid): l = mid + 1      else: r = mid - 1  return l

和最左最右二分这两种最最根本的类型相比，能力检测二分只是将 while 外部的 if 语句调整为了一个函数罢了。因而能力检测二分也分最左和最右两种根本类型。

基本上大家都能够用这个模式来套。明确了解题的框架，咱们最初来看下能力检测二分能够解决哪些问题。这里通过三道题目带大家感受一下，相似的题目还有很多，大家课后自行领会。

875. 爱吃香蕉的珂珂（中等）

题目地址

https://leetcode-cn.com/probl...

题目形容
珂珂喜爱吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫曾经来到了，将在 H 小时后回来。珂珂能够决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会抉择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，而后这一小时内不会再吃更多的香蕉。  珂珂喜爱缓缓吃，但依然想在警卫回来前吃掉所有的香蕉。返回她能够在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。 示例 1：输出: piles = [3,6,7,11], H = 8输入: 4示例 2：输出: piles = [30,11,23,4,20], H = 5输入: 30示例 3：输出: piles = [30,11,23,4,20], H = 6输入: 23 提醒：1 <= piles.length <= 10^4piles.length <= H <= 10^91 <= piles[i] <= 10^9
前置常识
  • 二分查找
公司
  • 字节
思路

题目是让咱们求H 小时内吃掉所有香蕉的最小速度。

合乎直觉的做法是枚举所有可能的速度，找出所有的能够吃完香蕉的速度，接下来抉择最小的速度即可。因为须要返回最小的速度，因而抉择从小到大枚举会比拟好，因为能够提前退出。 这种解法的工夫复杂度比拟高，为 $O(N * M)$，其中 N 为 piles 长度， M 为 Piles 中最大的数（也就是解空间的最大值）。

察看到须要检测的解空间是个有序序列，应该想到可能可能应用二分来解决，而不是线性枚举。能够应用二分解决的要害和后面咱们简化的二分问题并无二致，关键点在于如果速度 k 吃不完所有香蕉，那么所有小于等于 k 的解都能够被排除。

二分解决的关键在于：

  • 明确解空间。 对于这道题来说， 解空间就是 [1,max(piles)]。
  • 如何膨胀解空间。关键点在于如果速度 k 吃不完所有香蕉，那么所有小于等于 k 的解都能够被排除。

综上，咱们能够应用最左二分，即一直膨胀右边界。

香蕉堆的香蕉个数下限是 10^9， 珂珂这也太能吃了吧？
关键点解析
  • 二分查找模板
代码

代码反对：Python，JavaScript

Python Code:

class Solution:    def solve(self, piles, k):        def possible(mid):            t = 0            for pile in piles:                t += (pile + mid - 1) // mid            return t <= k        l, r = 1, max(piles)        while l <= r:            mid = (l + r) // 2            if possible(mid):                r = mid - 1            else:                l = mid + 1        return l

JavaScript Code:

function canEatAllBananas(piles, H, mid) {  let h = 0;  for (let pile of piles) {    h += Math.ceil(pile / mid);  }  return h <= H;}/** * @param {number[]} piles * @param {number} H * @return {number} */var minEatingSpeed = function (piles, H) {  let lo = 1,    hi = Math.max(...piles);  // [l, r) ， 左闭右开的益处是如果能找到，那么返回 l 和 r 都是一样的，因为最终 l 等于 r。  while (lo <= hi) {    let mid = lo + ((hi - lo) >> 1);    if (canEatAllBananas(piles, H, mid)) {      hi = mid - 1;    } else {      lo = mid + 1;    }  }  return lo; //  不能抉择hi};

复杂度剖析

  • 工夫复杂度：$O(max(N, N * logM))$，其中 N 为 piles 长度， M 为 Piles 中最大的数。
  • 空间复杂度：$O(1)$

最小灯半径（艰难）

题目形容
You are given a list of integers nums representing coordinates of houses on a 1-dimensional line. You have 3 street lights that you can put anywhere on the coordinate line and a light at coordinate x lights up houses in [x - r, x + r], inclusive. Return the smallest r required such that we can place the 3 lights and all the houses are lit up.Constraintsn ≤ 100,000 where n is the length of numsExample 1Inputnums = [3, 4, 5, 6]Output0.5ExplanationIf we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.
前置常识
  • 排序
  • 二分法
二分法
思路

本题和力扣 475. 供暖器 相似。

这道题的意思是给你一个数组 nums，让你在 [min(nums),max(nums)] 范畴内搁置 3 个灯，每个灯笼罩半径都是 r，让你求最小的 r。

之所以不抉择小于 min(nums) 的地位和大于 max(nums) 的地位是因为没有必要。比方选取了小于 min(nums) 的地位 pos，那么选取 pos 肯定不比抉择 min(nums) 地位后果更优。

这道题的外围点还是一样的思维模型，即：

  • 确定解空间。这里的解空间其实就是 r。不难看出 r 的下界是 0， 上界是 max(nums) - min(nums)。
没必要非常精准，只有不错过正确解即可，这个咱们在后面讲过，这里再次强调一下。
  • 对于上下界之间的所有可能 x 进行枚举（无妨从小到大枚举），查看半径为 x 是否能够笼罩所有，返回第一个能够笼罩所有的 x 即可。

留神到咱们是在一个有序序列进行枚举，因而应用二分就应该想到。可应用二分的外围点在于：如果 x 不行，那么小于 x 的所有半径都必然不行。

接下来的问题就是给定一个半径 x，判断其是否可笼罩所有的房子。

判断其是否可笼罩就是所谓的能力检测，我定义的函数 possible 就是能力检测。

首先对 nums 进行排序，这在前面会用到。 而后从左开始模仿搁置灯。先在 nums[0] + r 处搁置一个灯，其能够笼罩 [0, 2 * r]。因为 nums 曾经排好序了，那么这个等能够笼罩到的房间其实就是 nums 中坐标小于等于 2 * r 所有房间，应用二分查找即可。对于 nums 右侧的所有的房间咱们须要持续搁置灯，采纳同样的形式即可。

能力检测外围代码：

def possible(diameter):    start = nums[0]    end = start + diameter    for i in range(LIGHTS):        idx = bisect_right(nums, end)        if idx >= N:            return True        start = nums[idx]        end = start + diameter    return False

因为咱们想要找到满足条件的最小值，因而可间接套用最左二分模板。

代码

代码反对：Python3

Python3 Code:

class Solution:    def solve(self, nums):        nums.sort()        N = len(nums)        if N <= 3:            return 0        LIGHTS = 3        # 这里应用的是直径，因而最终返回须要除以 2        def possible(diameter):            start = nums[0]            end = start + diameter            for i in range(LIGHTS):                idx = bisect_right(nums, end)                if idx >= N:                    return True                start = nums[idx]                end = start + diameter            return False        l, r = 0, nums[-1] - nums[0]        while l <= r:            mid = (l + r) // 2            if possible(mid):                r = mid - 1            else:                l = mid + 1        return l / 2

复杂度剖析

令 n 为数组长度。

  • 工夫复杂度：因为进行了排序， 因而工夫复杂度大概是 $O(nlogn)$
  • 空间复杂度：取决于排序的空间耗费

778. 水位回升的泳池中游泳（艰难）

题目地址

https://leetcode-cn.com/probl...

题目形容
在一个 N x N 的坐标方格  grid 中，每一个方格的值 grid[i][j] 示意在地位 (i,j) 的平台高度。当初开始下雨了。当工夫为  t  时，此时雨水导致水池中任意地位的水位为  t 。你能够从一个平台游向周围相邻的任意一个平台，然而前提是此时水位必须同时吞没这两个平台。假设你能够霎时挪动有限间隔，也就是默认在方格外部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格外面。你从坐标方格的左上平台 (0，0) 登程。起码耗时多久你能力达到坐标方格的右下平台  (N-1, N-1)？示例 1:输出: [[0,2],[1,3]]输入: 3解释:工夫为 0 时，你位于坐标方格的地位为 (0, 0)。此时你不能游向任意方向，因为四个相邻方向平台的高度都大于以后工夫为 0 时的水位。等工夫达到 3 时，你才能够游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你能够游向坐标方格中的任意地位示例 2:输出: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]输入: 16解释:0 1 2 3 424 23 22 21 512 13 14 15 1611 17 18 19 2010 9 8 7 6最终的路线用加粗进行了标记。咱们必须等到工夫为 16，此时能力保障平台 (0, 0) 和 (4, 4) 是连通的提醒:2 <= N <= 50.grid[i][j] 位于区间 [0, ..., N*N - 1] 内。
前置常识
  • DFS
  • 二分
思路

首先明确一下解空间。不难得出，解空间是[0, max(grid)]，其中 max(grid) 示意 grid 中的最大值。

因而一个简略的思路是一个个试。

  • 试试 a 能够不
  • 试试 a+1 能够不
  • 。。。

试试 x 是否可行就是能力检测。

实际上，如果 x 不能够，那么小于 x 的所有值都是不能够的，这正是本题的突破口。基于此，咱们同样可应用讲义中的最左二分模板解决。

伪代码:

def test(x):    passwhile l <= r:    mid = (l + r) // 2    if test(mid, 0, 0):        r = mid - 1    else:        l = mid + 1return l

这个模板会在很多二分中应用。比方典型的计数型二分，典型的就是计算小于等于 x 的有多少，而后依据答案更新解空间。

明确了这点，剩下要做的就是实现能力检测局部 （test 函数） 了。其实这个就是一个一般的二维网格 dfs，咱们从 (0,0) 开始在一个二维网格中搜寻，直到无奈持续或达到 (N-1,N-1)，如果能够达到 (N-1,N-1)，咱们返回 true，否则返回 False 即可。对二维网格的 DFS 不相熟的同学能够看下我之前写的小岛专题

代码
class Solution:    def swimInWater(self, grid: List[List[int]]) -> int:        l, r = 0, max([max(vec) for vec in grid])        seen = set()        def test(mid, x, y):            if x > len(grid) - 1 or x < 0 or y > len(grid[0]) - 1 or y < 0:                return False            if grid[x][y] > mid:                return False            if (x, y) == (len(grid) - 1, len(grid[0]) - 1):                return True            if (x, y) in seen:                return False            seen.add((x, y))            ans = test(mid, x + 1, y) or test(mid, x - 1,                                              y) or test(mid, x, y + 1) or test(mid, x, y - 1)            return ans        while l <= r:            mid = (l + r) // 2            if test(mid, 0, 0):                r = mid - 1            else:                l = mid + 1            seen = set()        return l

复杂度剖析

  • 工夫复杂度：$O(NlogM)$，其中 M 为 grid 中的最大值， N 为 grid 的总大小。
  • 空间复杂度：$O(N)$，其中 N 为 grid 的总大小。

计数二分

计数二分和下面的思路曾经代码都基本一致。 间接看代码会分明一点：

def count_bs(nums, k):  def count_not_greater(mid):    pass  l, r = 0, len(A) - 1  while l <= r:      mid = (l + r) // 2      # 只有这里和最左二分不一样      if count_not_greater(mid) > k: r = mid - 1      else: l = mid + 1  return l

能够看出只是将 possible 变成了 count_not_greater，返回值变成了数字而已。

实际上，咱们能够将下面的代码略微革新一下，使得两者更像：

def count_bs(nums, k):  def possible(mid, k):    # xxx    return cnt > k  l, r = 0, len(A) - 1  while l <= r:      mid = (l + r) // 2      if possible(mid, k): r = mid - 1      else: l = mid + 1  return l

是不是基本一致了？

因为和下面基本一致， 因而这里间接举荐一个题目，大家用我的思路练习一下，看看我的技巧灵不灵。

  • 第 k 小的间隔对

前缀和二分

后面说了：如果数组全是正的，那么其前缀和就是一个严格递增的数组，基于这个个性，咱们能够在其之上做二分。相似的有枯燥栈/队列。这种题目类型很多，为了节俭篇幅就不举例说明了。提出前缀和二分的外围的点在于让大家放弃对有序序列的敏感度。

插入排序二分

除了下面的前缀和之外，咱们还能够自行保护有序序列。个别有两种形式：

  • 间接对序列排序。

代码示意：

nums.sort()bisect.bisect_left(nums, x) # 最左二分bisect.bisect_right(nums, x) # 最右二分
  • 遍历过程保护一个新的有序序列，有序序列的内容为曾经遍历过的值的汇合。

比方无序数组 [3,2,10,5]，遍历到索引为 2 的项（也就是值为 10 的项）时，咱们构建的有序序列为 [2,3,10]。

留神我形容的是有序序列，并不是指数组，链表等具体的数据结构。而实际上，这个有序序列很多状况下是均衡二叉树。前面题目会体现这一点。

代码示意：

d = SortedList()for a in A:    d.add(a) # 将 a 增加到 d，并维持 d 中数据有序

下面代码的 d 就是有序序列。

理论知识到此为止，接下来通过一个例子来阐明。

327. 区间和的个数(艰难)

题目地址

https://leetcode-cn.com/probl...

题目形容
给定一个整数数组 nums 。区间和 S(i, j) 示意在 nums 中，地位从 i 到 j 的元素之和，蕴含 i 和 j (i ≤ j)。请你以下标 i （0 <= i <= nums.length ）为终点，元素个数逐次递增，计算子数组内的元素和。当元素和落在范畴 [lower, upper] （蕴含 lower 和 upper）之内时，记录子数组以后最末元素下标 j ，记作 无效 区间和 S(i, j) 。求数组中，值位于范畴 [lower, upper] （蕴含 lower 和 upper）之内的 无效 区间和的个数。 留神：最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。 示例：输出：nums = [-2,5,-1], lower = -2, upper = 2,输入：3解释：下标 i = 0 时，子数组 [-2]、[-2,5]、[-2,5,-1]，对应元素和别离为 -2、3、2 ；其中 -2 和 2 落在范畴 [lower = -2, upper = 2] 之间，因而记录无效区间和 S(0,0)，S(0,2) 。下标 i = 1 时，子数组 [5]、[5,-1] ，元素和 5、4 ；没有满足题意的无效区间和。下标 i = 2 时，子数组 [-1] ，元素和 -1 ；记录无效区间和 S(2,2) 。故，共有 3 个无效区间和。 提醒：0 <= nums.length <= 10^4
思路

题目很好了解。

由前缀和的性质晓得：区间 i 到 j（蕴含）的和 sum(i,j) = pre[j] - pre[i-1]，其中 pre[i] 为数组前 i 项的和 0 <= i < n。

然而题目中的数字可能是正数，前缀和不肯定是枯燥的啊？这如何是好呢？答案是手动保护前缀和的有序性。

比方 [-2,5,-1] 的前缀和 为 [-2,3,2]，然而咱们能够将求手动保护为 [-2,2,3]，这样就有序了。然而这丢失了索引信息，因而这个技巧仅实用于无需思考索引，也就是不需要求具体的子序列，只须要晓得有这么一个子序列就行了，具体是哪个，咱们不关怀。

比方以后的前缀和是 cur，那么前缀和小于等于 cur - lower 有多少个，就阐明以以后结尾的区间和大于等于 lower 的有多少个。相似地，前缀和小于等于 cur - upper 有多少个，就阐明以以后结尾的区间和大于等于 upper 的有多少个。

基于这个想法，咱们可应用二分在 $logn$ 的工夫疾速求出这两个数字，应用均衡二叉树代替数组可使得插入的工夫复杂度升高到 $O(logn)$。Python 可应用 SortedList 来实现， Java 可用 TreeMap 代替。

代码
from sortedcontainers import SortedListclass Solution:    def countRangeSum(self, A: List[int], lower: int, upper: int) -> int:        ans, pre, cur = 0, [0], 0        for a in A:            cur += a            ans += pre.bisect_right(cur - lower) - pre.bisect_left(cur - upper)            pre.add(cur)        return ans

复杂度剖析

令 n 为数组长度。

  • 工夫复杂度：$O(nlogn)$
  • 空间复杂度：$O(nlogn)$

493. 翻转对（艰难）

题目地址

https://leetcode-cn.com/probl...

题目形容
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 咱们就将 (i, j) 称作一个重要翻转对。你须要返回给定数组中的重要翻转对的数量。示例 1:输出: [1,3,2,3,1]输入: 2示例 2:输出: [2,4,3,5,1]输入: 3留神:给定数组的长度不会超过50000。输出数组中的所有数字都在32位整数的示意范畴内。
前置常识
  • 二分
公司
  • 暂无
思路

咱们能够一边遍历一边保护一个有序序列 d，其中 d 为曾经遍历过的值的汇合。对于每一个地位 0 <= i < n，咱们统计 d 中大于 2 * A[i] 的个数，这个个数就是题目要求的翻转对。这里的关键在于 d 中的值是比以后索引小的全副值。

咱们当然能够线性遍历 d，求出个数。一个更好的办法是在遍历的同时维持 d 是有序的，这样咱们就能够用二分了。和下面题目一样，应用均衡二叉树代替数组可使得插入的工夫复杂度升高到 $O(logn)$。

关键点
  • 插入排序二分
代码
  • 语言反对：Python3

Python3 Code:

from sortedcontainers import SortedListclass Solution:    def reversePairs(self, A: List[int]) -> int:        d = SortedList()        ans = 0        for a in A:            ans += len(d) - d.bisect_right(2*a)            d.add(a)        return ans

复杂度剖析

令 n 为数组长度。

  • 工夫复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$

小结

四个利用讲了两种结构有序序列的形式，别离是前缀和，插入排序，插入排序的局部其实也能够看下我之前写的最长回升子序列系列，那外面的贪婪解法就是本人结构有序序列再二分的。 另外实践上枯燥栈/队列也是有序的，也可是用来做二分，然而相干题目太少了，因而大家只有放弃对有序序列的敏感度即可。

能力检测二分很常见，不过其仅仅是将一般二分的 if 局部革新成了函数而已。而对于计数二分，其实就是能力检测二分的特例，只不过其太常见了，就将其独自提取进去了。

另外，有时候有序序列也会给你略微变动一种模式。比方二叉搜寻树，大家都晓得能够在 $logn$ 的工夫实现查找，这个查找过程实质也是二分。二叉查找树有有序序列么？有的！二叉查找树的中序遍历恰好就是一个有序序列。因而如果一个数比以后节点值小，肯定在左子树（也就是有序序列的左侧），如果一个数比以后节点值大，肯定在右子树（也就是有序序列的右侧）。

总结

本文次要讲了两种二分类型：最左和最右，模板曾经给大家了，大家只须要依据题目调整解空间和判断条件即可。对于四种利用更多的还是让大家了解二分的外围折半。外表上来看，二分就是对有序序列的查找。其实不然，只不过有序序列很容易做二分罢了。因而战术上大家放弃对有序序列的敏感度，策略上要明确二分的实质是折半，外围在于什么时候将哪一半折半。

一个问题是否用二分解决的关键在于检测一个值的时候是否能够排除解空间中的一半元素。比方我后面重复提到的如果 x 不行，那么解空间中所有小于等于 x 的值都不行。

对于简略题目，通常就是给你一个有序序列，让你在下面找满足条件的地位。顶多变动一点，比方数组部分有序，一维变成二维等。对于这部分能够看下我写的91 算法 - 二分查找讲义

中等题目可能须要让你本人结构有序序列。

艰难题则可能是二分和其余专题的联合，比方下面的 778. 水位回升的泳池中游泳（艰难），就是二分和搜寻（我用的是 DFS）的联合。

以上就是本文的全部内容了， 大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。我是 lucifer，保护西湖区最好的算法题解，Github 超 40K star 。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

另外我整顿的 1000 多页的电子书已限时收费下载，大家能够去我的公众号《力扣加加》后盾回复电子书获取。