关于算法:几乎刷完了力扣所有的二分题我发现了这些

前言

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

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

本系列蕴含以下专题：

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

<!– more –>

本专题预计分两局部两进行。第一局部次要讲述 基本概念 和 一个核心 。有了这些基础知识之后，第二局部咱们持续学习 两种二分类型 和 四大利用。

本文内容曾经同步到我的刷题插件的 RoadMap 中，联合刷题插件食用滋味更佳哦~ 插件的获取形式能够在我的公众号力扣加加中回复插件查看。

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

前言

为了筹备这个专题，我不仅肝完了力扣的所有二分题目，还肝完了另外一个 OJ 网站 – Binary Search 的所有二分题目，一共100 多道。大家看完如果感觉有用，能够通过点赞转发的形式通知我，如果喜爱的人多，我持续尽快出下篇哦~

二分查找又称 折半搜索算法。广义地来讲，二分查找是一种在有序数组查找某一特定元素的搜索算法。这同时也是大多数人所晓得的一种说法。实际上，狭义的二分查找是将问题的规模放大到原有的一半。相似的，三分法就是将问题规模放大为原来的 1/3。

本文给大家带来的内容则是 广义地二分查找，如果想理解其余狭义上的二分查找能够查看我之前写的一篇博文 从老鼠试毒问题来看二分法

只管二分查找的根本思维绝对简略，但细节能够令人难以招架 … — 高德纳

当乔恩·本特利将二分搜寻问题安排给业余编程课的学生时，百分之 90 的学生在破费数小时后还是无奈给出正确的解答，次要因为这些谬误程序在面对边界值的时候无奈运行，或返回谬误后果。1988 年发展的一项钻研显示，20 本教科书里只有 5 本正确实现了二分搜寻。不仅如此，本特利本人 1986 年出版的《编程珠玑》一书中的二分搜索算法存在整数溢出的问题，二十多年来无人发现。Java 语言的库所实现的二分搜索算法中同样的溢出问题存在了九年多才被修复。

可见二分查找并不简略，本文就试图带你走近 ta，明确 ta 的底层逻辑，并提供模板帮忙大家写书 bug free 的二分查找代码。看完讲义后倡议大家联合 LeetCode Book 二分查找 练习一下。

基本概念

首先咱们要晓得几个基本概念。这些概念对学习二分有着很重要的作用，之后遇到这些概念就不再讲述了，默认大家曾经把握。

解空间

解空间指的是 题目所有可能的解形成的汇合 。比方一个题目所有解的可能是 1,2,3,4,5，但具体在某一种状况只能是其中某一个数（即可能是 1，2，3，4，5 中的 一个数 ）。那么这里的解空间就是 1,2,3,4,5 形成的汇合，在某一个具体的状况下可能是其中任意一个值， 咱们的指标就是在某个具体的状况判断其具体是哪个。如果线性枚举所有的可能，就枚举这部分来说工夫复杂度就是 $O(n)$。

举了例子：

如果让你在一个数组 nums 中查找 target，如果存在则返回对应索引，如果不存在则返回 -1。那么对于这道题来说其解空间是什么？

很显著解空间是区间 [-1, n-1]，其中 n 为 nums 的长度。

须要留神的是下面题目的解空间只可能是区间 [-1,n-1] 之间的整数。而诸如 1.2 这样的小数是不可能存在的。这其实也是大多数二分的状况。但也有少部分题目解空间包含小数的。如果解空间包含小数，就可能会波及到精度问题，这一点大家须要留神。

比方让你求一个数 x 的平方根，答案误差在 $10^-6$ 次方都认为正确。这里容易晓得其解空间大小可定义为 [1,x]（当然能够定义地更准确，之后咱们再探讨这个问题），其中解空间应该包含所有区间的实数，不仅仅是整数而已。这个时候解题思路和代码都没有太大变动，唯二须要变动的是：

1. 更新答案的步长。比方之前的更新是 l = mid + 1，当初 可能 就不行了，因而这样 可能 会错过正确解，比方正确解恰好就在区间 [mid,mid+1] 内的某一个小数。
2. 判断条件时候须要思考误差。因为精度的问题，判断的完结条件可能就要变成 与答案的误差在某一个范畴内。

对于 搜寻类题目 ，解空间肯定是无限的，不然问题不可解。对于搜寻类问题，第一步就是须要明确解空间，这样你才可能在解空间内进行搜寻。这个技巧不仅实用于二分法，只有是搜寻问题都能够应用，比方 DFS，BFS 以及回溯等。只不过对于二分法来说， 明确解空间显得更为重要。如果当初还不了解这句话也没关系，看完本文或者你就了解了。

定义解空间的时候的一个准则是：能够大但不能够小。因为如果解空间偏大（只有不是无限大）无非就是多做几次运算，而如果解空间过小则可能 错失正确解，导致后果谬误。比方后面我提到的求 x 的平方根，咱们当然能够将解空间定义的更小，比方定义为 [1,x/2]，这样能够缩小运算的次数。但如果设置地太小，则可能会错过正确解。这是老手容易犯错的点之一。

有的同学可能会说我看不出来怎么办呀。我感觉如果你切实拿不准也齐全没有关系，比方求 x 的平方根，就能够甚至为 [1,x]，就让它多做几次运算嘛。我倡议你 给上下界设置一个宽泛的范畴 。等你对二分逐渐理解之后能够 卡地更死一点。

序列有序

我这里说的是序列，并不是数组，链表等。也就是说二分法通常要求的序列有序，不肯定是数组，链表，也有可能是其余数据结构。另外有的 序列有序 题目间接讲进去了，会比拟容易。而有些则暗藏在题目信息之中。乍一看，题目并没有 有序 关键字，而有序其实就暗藏在字里行间。比方题目给了数组 nums，并且没有限定 nums 有序，但限定了 nums 为非负。这样如果给 nums 做前缀和或者前缀或（位运算或），就能够失去一个有序的序列啦。

更多技巧在四个利用局部开展哦。

尽管二分法不意味着须要序列有序，但大多数二分题目都有 有序 这个显著特色。只不过：

• 有的是题目间接限定了有序。这种题目通常难度不高，也容易让人想到用二分。
• 有的是须要你 本人结构有序序列。这种类型的题目通常难度不低，须要大家有肯定的察看能力。

比方 Triple Inversion。题目形容如下：

Given a list of integers nums, return the number of pairs i < j such that nums[i] > nums[j] * 3.

Constraints：n ≤ 100,000 where n is the length of nums
Example 1
Input：nums = [7, 1, 2]
Output：2
Explanation：We have the pairs (7, 1) and (7, 2)

这道题并没有限定数组 nums 是有序的，然而咱们能够结构一个有序序列 d，进而在 d 上做二分。代码：

class Solution:
    def solve(self, A):
        d = []
        ans = 0

        for a in A:
            i = bisect.bisect_right(d, a * 3)
            ans += len(d) - i
            bisect.insort(d, a)
        return ans

如果临时不了解代码也没关系，大家先留个印象，晓得有这么一种类型题即可，大家能够看完本章的所有内容（高低两篇）之后再回头做这道题。

极值

相似我在堆专题 提到的极值。只不过这里的极值是 动态的 ，而不是动静的。这里的极值通常指的是 求第 k 大（或者第 k 小）的数。

堆的一种很重要的用法是求第 k 大的数，而二分法也能够求第 k 大的数，只不过 二者的思路齐全不同。应用堆求第 k 大的思路我曾经在后面提到的堆专题里具体解释了。那么二分呢？这里咱们通过一个例子来感受一下：这道题是 Kth Pair Distance，题目形容如下：

Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.

Constraints:n ≤ 100,000 where n is the length of nums
Example 1
Input:
nums = [1, 5, 3, 2]
k = 3
Output:
2
Explanation:

Here are all the pair distances:

abs(1 - 5) = 4
abs(1 - 3) = 2
abs(1 - 2) = 1
abs(5 - 3) = 2
abs(5 - 2) = 3
abs(3 - 2) = 1

Sorted in ascending order we have [1, 1, 2, 2, 3, 4].

简略来说，题目就是给的一个数组 nums，让你求 nums 第 k 大的 任意两个数的差的绝对值。当然，咱们能够应用堆来做，只不过应用堆的工夫复杂度会很高，导致无奈通过所有的测试用例。这道题咱们能够应用二分法来降维打击。

对于这道题来说，解空间就是从 0 到数组 nums 中最大最小值的差，用区间示意就是 [0, max(nums) – min(nums)]。明确理解空间之后，咱们就须要对解空间进行二分。对于这道题来说，能够选以后解空间的两头值 mid，而后计算小于等于这个两头值的 任意两个数的差的绝对值 有几个，咱们无妨令这个数字为 x。

• 如果 x 大于 k，那么解空间中大于等于 mid 的数都不可能是答案，能够将其舍弃。
• 如果 x 小于 k，那么解空间中小于等于 mid 的数都不可能是答案，能够将其舍弃。
• 如果 x 等于 k，那么 mid 就是答案。

基于此，咱们可应用二分来解决。这种题型，我总结为 计数二分。我会在前面的四大利用局部重点解说。

代码：

class Solution:
    def solve(self, A, k):
        A.sort()
        def count_not_greater(diff):
            i = ans = 0
            for j in range(1, len(A)):
                while A[j] - A[i] > diff:
                    i += 1
                ans += j - i
            return ans
        l, r = 0, A[-1] - A[0]

        while l <= r:
            mid = (l + r) // 2
            if count_not_greater(mid) > k:
                r = mid - 1
            else:
                l = mid + 1
        return l

如果临时不了解代码也没关系，大家先留个印象，晓得有这么一种类型题即可，大家能够看完本章的所有内容（高低两篇）之后再回头做这道题。

一个核心

二分法的一个核心大家肯定牢牢记住。其余（比方序列有序，左右双指针）都是二分法的手和脚，都是表象，并不是实质，而 折半才是二分法的灵魂。

后面曾经给大家明确理解空间的概念。而这里的折半其实就是解空间的折半。

比方刚开始解空间是 [1, n]（n 为一个大于 n 的整数）。通过 某种形式 ，咱们确定 [1, m] 区间都 不可能是答案。那么解空间就变成了 (m,n]，继续此过程晓得解空间变成平庸（间接可解）。

留神区间 (m,n] 左侧是凋谢的，示意 m 不可能取到。

显然折半的难点是 依据什么条件舍弃哪一步局部。这里有两个关键字:

1. 什么条件
2. 舍弃哪局部

简直所有的二分的难点都在这两个点上。如果明确了这两点，简直所有的二分问题都能够迎刃而解。侥幸的是，对于这两个问题的答案通常都是无限的，题目考查的往往就是那几种。这其实就是所谓的做题套路。对于这些套路，我会在之后的四个利用局部给大家做具体介绍。

二分法上篇小结

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

如果让我用一句话总结二分法，我会说 二分法是一种让未知世界无机可乘的算法 。即二分法无论如何咱们都能够舍弃一半解，也就是无论如何都能够将解空间砍半。难点就是下面提到的两点： 什么条件 和 舍弃哪局部。这是二分法外围要解决的问题。

以上就是《二分专题（上篇）》的所有内容。如果感觉文章有用，请点赞留言转发一下，让我有能源持续出下集。

下集预报

上集介绍的是基本概念。下一集咱们介绍两种二分的类型以及四种二分的利用。

下集目录：

• 两种类型

  • 最左插入
  • 最右插入

• 四大利用

  • 能力检测二分
  • 前缀和二分
  • 插入排序二分（不是你了解的插入排序哦）
  • 计数二分

其中两种类型（最左和最右插入）次要解决的的是：解空间曾经明确进去了，如何用代码找出具体的解。

而四大利用次要解决的是：如何结构解空间。更多的状况则是如何构建有序序列。

这两局部都是实操性很强的内容，在了解这两局部内容的同时，请大家务必牢记一个核心 折半。那咱们下篇见喽~

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