二分查找的底层逻辑解空间、有序性与折半中心思想【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode二分查找Binary Search又称折半搜索看似简单却被称为最容易写错的算法之一。本文以本仓库《二分专题上》讲义为核心系统讲解二分查找的三大基本概念解空间、序列有序、极值与一个中心思想折半并延伸至仓库配套讲义中的两种类型模板与四大应用帮助你建立从明确解空间到用代码砍半解空间的完整方法论写出 bug free 的二分代码。本文内容对应仓库讲义 thinkings/binary-search-1.en.md并补充了其姊妹篇 thinkings/binary-search-2.en.md 与 91/binary-search.md 中的模板与例题。一、为什么二分查找看似简单实则致命尽管二分查找的基本思想相对简单但细节可以令人难以招架——这句话出自高德纳Donald Knuth。仓库讲义在开篇就给出了一组令人警醒的历史事实当 Jon Bentley 将二分搜索问题布置给专业编程课的学生时90% 的学生在花费数小时后仍无法给出正确解答主要原因是这些程序在面对边界值时无法运行或返回错误结果。1988 年的一项研究显示20 本教科书中只有 5 本正确实现了二分搜索。Bentley 本人 1986 年出版的《编程珠玑》一书中的二分搜索算法存在整数溢出问题二十多年无人发现。Java 语言库中实现的二分搜索算法存在同样的溢出问题存在了九年多才被修复。这些事故的根源在于二分算法的循环终止条件、区间开闭形式、mid 的取整方向任何一个细节出错都会在边界场景下悄悄返回错误结果。为此本专题的目标是先讲清几个核心概念再提炼一个中心最后给出可直接套用的代码模板。二、基本概念之一解空间Solution Space2.1 什么是解空间解空间指的是题目所有可能的解构成的集合。例如某题的所有可能解是 1、2、3、4、5在某个具体输入下答案只能是其中之一那么这个题目的解空间就是集合 {1,2,3,4,5}我们的目标是在某个具体情况下判断答案到底是哪一个。如果线性枚举所有可能仅枚举部分的时间复杂度就是 $O(n)$。举个仓库讲义中的例子在一个数组nums中查找target存在则返回索引不存在返回 -1。这道题的解空间是什么很明显是区间[-1, n-1]其中n为nums的长度。2.2 整数解空间与小数解空间需要注意上述题目的解空间只可能是[-1, n-1]之间的整数1.2 这样的小数不可能存在。这其实是大多数二分的情况。但也有少数题目的解空间包含小数此时就会涉及精度问题。例如求一个数x的平方根答案误差在 $10^{-6}$ 以内即认为正确。此时解空间可定义为[1, x]当然可以定义得更精确且解空间应包含区间内所有实数不仅仅是整数。解题思路和代码都没有太大变化唯二需要变化的是更新答案的步长。比如之前更新是l mid 1现在可能就不行了因为这样可能会错过正确解——比如正确解恰好落在区间[mid, mid1]内的某个小数。判断条件需要考虑误差。由于精度问题结束条件可能要变成与答案的误差在某一范围内。2.3 定义解空间的原则可以大但不可以小对于搜索类题目解空间一定是有限的否则问题不可解。搜索类问题的第一步就是明确解空间这样才能在解空间内进行搜索。这个技巧不仅适用于二分只要是搜索问题DFS、BFS、回溯都适用只不过对二分来说明确解空间显得更为重要。定义解空间时的一个原则是可以大但不可以小。如果解空间偏大只要不是无限大无非多做几次运算如果解空间过小则可能错失正确解导致结果错误。例如求x的平方根可以把解空间定义为更小的[1, x/2]以减少运算次数但如果设置得太小就可能错过正确解——这是新手容易犯的错误之一。如果拿不准直接设置一个宽泛的范围如[1, x]多跑几次运算即可等对二分理解深入后再把边界卡得更死。三、基本概念之二序列有序Ordered Sequence3.1 序列不一定是数组讲义强调这里说的是序列并不是数组、链表等具体数据结构。二分法通常要求序列有序但序列不一定是数组也可能是其他数据结构。有序序列的来源分两种题目直接限定有序。这类题目通常难度不高也容易让人想到用二分。需要自己构造有序序列。这类题目通常难度不低需要一定的观察能力。有些题目乍一看没有有序关键字但有序其实隐藏在字里行间。例如题目给了数组nums没有限定nums有序但限定了nums为非负——这样给nums做前缀和或前缀或位运算或就可以得到一个有序序列。3.2 实战例Triple Inversion讲义以 Triple Inversion 为例。题目描述problems/Triple-Inversion.mdGiven 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这里d维护的是已经遍历过的值的有序集合每次用bisect_right二分求出d中大于a * 3的个数并累加再把a插入d保持有序。如果暂时不理解代码也没关系先留个印象——知道存在自己构造有序序列再二分这一类型题等学完两种类型与四大应用后可以回头再刷这道题。四、基本概念之三极值Extreme Value4.1 堆求第 k 大 vs 二分求第 k 大讲义在堆专题中提过极值的概念只不过这里的极值是静态的不是动态的通常指求第 k 大或第 k 小的数。堆的一种重要用途是求第 k 大的数而二分法同样可以求第 k 大的数但二者思路完全不同。使用堆求第 k 大的思路已在堆专题中详细解释二分的思路则通过下面的例子来感受。4.2 实战例Kth Pair Distance计数二分的雏形题目描述problems/Kth-Pair-Distance.mdGiven 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中任意两个数的差的绝对值中第 k 小的那个。当然可以用堆来做但时间复杂度会很高无法通过所有测试用例。这道题可以用二分法降维打击明确解空间解空间是从 0 到数组最大值与最小值之差即[0, max(nums) - min(nums)]。对解空间二分取当前解空间的中间值mid计算小于等于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这种通过计数来判断如何收缩解空间的题型讲义总结为计数二分会在四大应用部分重点讲解对应姊妹篇 thinkings/binary-search-2.en.md。五、一个中心折半Halving5.1 折半才是二分法的灵魂请务必牢牢记住二分法的一个中心其他一切序列有序、左右双指针都是二分法的手和脚都是表象而非本质折半才是二分法的灵魂。前面已经明确了解空间的概念而这里的折半其实就是解空间的折半。例如刚开始解空间是[1, n]通过某种方式我们确定[1, m]区间都不可能是答案那么解空间就变成了(m, n]持续此过程直到解空间变成平凡直接可解。注意区间(m, n]左侧是开放的表示m不可能取到。5.2 折半的难点什么条件、舍弃哪部分显然折半的难点是根据什么条件舍弃哪一部分这里有两个关键字什么条件判断依据舍弃哪部分收缩方向几乎所有的二分难点都落在这两个点上。如果明确了这两点几乎所有的二分问题都可以迎刃而解。幸运的是这两个问题的答案通常是有限的题目考察的往往就是那几种——这其实就是所谓的做题套路四大应用部分会做详细介绍。5.3 一句话总结如果要用一句话总结二分法可以这样说二分法是一种让未知世界无机可乘的算法——无论如何我们都可以舍弃一半解也就是无论如何都可以将解空间砍半。难点就是上面提到的两点什么条件、舍弃哪部分。六、从概念到模板两种二分类型讲义上篇预告解空间已经明确之后需要解决如何用代码找出具体的解——这就是两种类型最左插入、最右插入要解决的问题。仓库的 91/binary-search.md 与 thinkings/binary-search-2.en.md 给出了完整模板这里先看最基础的查找一个数。6.1 查找一个数基础模板算法描述以nums [1,3,4,6,7,8,10,13,14]target 4为例先从数组的中间元素开始如果中间元素正好是要查找的元素搜索结束如果目标元素大于中间元素则数组中小于中间元素的值都可以排除数组有序等价于排除数组左侧所有值解空间收缩为[mid1, r]如果目标元素小于中间元素则数组中大于中间元素的值都可以排除解空间收缩为[l, mid-1]如果在某一步骤解空间为空则代表找不到。具体走查中间元素为 77 47 右边的数字都大于 7不可能是答案范围缩到 7 左侧解空间变为[1,3,4,6]中间元素为 33 43 左边的数字都小于 3范围缩到 3 右侧解空间变为[4,6]中间元素为 4正好是目标返回其索引 2。复杂度分析由于每次比较都使搜索范围缩小一半是典型的二分查找。平均时间复杂度$O(\log N)$最坏时间复杂度$O(\log N)$空间复杂度迭代 $O(1)$递归 $O(\log N)$无尾调用消除思维框架这是写出 bug free 代码的关键首先定义解空间为[left, right]注意是左右都闭合之后会用到这个点。由于解空间为[left, right]当left right时解空间都不为空此时都需要继续搜索——即终止搜索条件为left right。举例对于区间[4,4]其包含元素 4解空间不为空需要继续搜索试想 4 恰好是 target如果不继续搜索就会错过正确答案而当解空间为[left, right)时同样对[4,4]此时解空间是空的因为这样的区间不存在任何数字。循环体内不断计算mid并将nums[mid]与目标值比对相等则提前返回mid小于目标值则解空间缩小为[mid1, right]大于目标值则解空间缩小为[left, mid-1]。循环结束都没找到返回 -1。四种语言模板来自 91/binary-search.md// 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) left mid 1; // 解空间变为 [mid1, right] if (nums[mid] target) right mid - 1; // 解空间变为 [left, mid-1] } return -1; }# Python def binarySearch(nums, target): # 左右都闭合的区间 [l, r] l, r 0, len(nums) - 1 while l r: mid (l r) 1 if nums[mid] target: return mid if nums[mid] target: l mid 1 # 解空间变为 [mid1, right] if nums[mid] target: r mid - 1 # 解空间变为 [left, 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) left mid 1; // 解空间变为 [mid1, right] if (nums[mid] target) right mid - 1; // 解空间变为 [left, mid-1] } return -1; }// C int binarySearch(vectorint 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; } else if(nums[mid] target) left mid 1; // 解空间变为 [mid1, right] else right mid - 1; // 解空间变为 [left, mid-1] } return -1; }注意mid left (right - left) / 2这种写法直接写(left right) / 2在极端大数下可能溢出这也是《编程珠玑》和 Java 库曾犯过的错误。用left (right - left) / 2或右移一位可以规避整数溢出。6.2 寻找最左插入位置最左二分查找一个数找不到就返回 -1。如果改为返回应该插入的位置使得插入之后列表仍然有序就变成了寻找最左插入位置。例如数组nums: [1,3,4]target 2应插入注意不是真的插入的位置是索引 1即[1, 2, 3, 4]因此寻找最左插入位置应返回 1而寻找满足条件的位置应返回 -1。另外如果有多个满足条件的值返回最左侧的例如nums: [1,2,2,2,3,4]target 2应插入的位置是 1。思维框架等价于寻找最左满足 target的位置。定义解空间为[left, right]左右都闭合终止搜索条件为left right当A[mid] x说明找到一个备胎令r mid - 1将mid从解空间排除继续看看有没有更好的备胎当A[mid] x说明mid根本不是答案直接更新l mid 1将mid从解空间排除最后解空间的l就是最好的备胎备胎转正。def bisect_left(A, x): # 内置 api bisect.bisect_left(A, 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 l6.3 寻找最右插入位置最右二分思维框架等价于寻找最右满足 target的位置的右邻居。当A[mid] x说明找到一个备胎令r mid - 1继续寻找更好的备胎当A[mid] x说明mid不是答案更新l mid 1最后解空间的l或r 1就是最好的备胎。def bisect_right(A, x): # 内置 api bisect.bisect_right(A, 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 # 或者 r 16.4 为什么只需要掌握最左、最右两种类型讲义强调实际写代码时不要用寻找满足条件的值模板而是直接用最左或最右插入模板。因为后者包含了前者并拥有前者实现不了的功能要实现寻找满足条件的值可直接用最左插入模板找到插入索引i最后判断nums[i]是否等于target即可——不等则返回 -1相等则返回i。这也是把二分划分为两种类型而非三种甚至四种的原因。最左插入与最右插入结合使用可以求出有序序列中和target相等的数的个数这在某些时候是考点nums [1,2,2,2,3,4] i bisect.bisect_left(nums, 2) # get 1 j bisect.bisect_right(nums, 2) # get 4 # j - i 就是 nums 中 2 的个数用两句话总结两种类型的核心最左二分不断收缩右边界最终返回左边界最右二分不断收缩左边界最终返回右边界。七、四大应用如何构造解空间解空间明确后如何用代码求解由两种类型解决而如何构造解空间更多情况是如何构建有序序列则由四大应用解决。以下内容对应 thinkings/binary-search-2.en.md。7.1 能力检测二分能力检测二分一般是定义函数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. 爱吃香蕉的珂珂仓库题解见 problems/875.koko-eating-bananas.md配图见 assets/problems/koko-eating-bananas.png题目描述有 N 堆香蕉第 i 堆有piles[i]根警卫 H 小时后回来。珂珂每小时选一堆吃掉 K 根不足 K 根则吃完该堆且该小时内不再多吃求在 H 小时内吃完所有香蕉的最小速度 K。约束1 piles.length 10^4piles.length H 10^91 piles[i] 10^9。符合直觉的做法是枚举所有可能速度从小到大枚举找出最小可行速度时间复杂度为 $O(N \times M)$N 为 piles 长度M 为 piles 中最大数。但观察到需要检测的解空间是个有序序列应想到用二分。二分的核心在于如果速度 k 吃不完所有香蕉那么所有小于等于 k 的解都可以被排除。于是解空间为[1, max(piles)]使用最左二分不断收缩右边界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 lJavaScript 版本来自仓库题解function canEatAllBananas(piles, H, mid) { let h 0; for (let pile of piles) { h Math.ceil(pile / mid); } return h H; } var minEatingSpeed function (piles, H) { let lo 1, hi Math.max(...piles); 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 \cdot \log M))$N 为 piles 长度M 为 piles 中最大数空间复杂度 $O(1)$。7.2 计数二分计数二分与能力检测二分的思路和代码基本一致只是把possible变成了count_not_greater返回值从布尔值变成了数字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定义为返回cnt k的布尔函数即可。本质上计数二分就是能力检测二分的特例只是它太常见了被单独提取出来。典型题目如 Kth Pair Distance见上文第四节可以用此思路练习。7.3 前缀和二分前面提到如果数组全是正的那么其前缀和就是一个严格递增的数组基于这个特性可以在其上做二分。类似的有单调栈/队列。前缀和二分提出的核心点在于让大家保持对有序序列的敏感度。例如题目给出数组nums且限定nums非负那么nums的前缀和或前缀或就是一个有序序列直接在其上二分即可。7.4 插入排序二分除了前缀和之外我们还可以自行维护有序序列。一般有两种方式直接对序列排序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 中数据有序典型例题493. 翻转对困难仓库题解见 problems/493.reverse-pairs.md。给定数组nums如果i j且nums[i] 2*nums[j]就将(i, j)称作一个重要翻转对返回重要翻转对的数量。一边遍历一边维护一个有序序列d已经遍历过的值的集合对于每个位置统计d中大于2 * A[i]的个数。用平衡二叉树代替数组可将插入复杂度降到 $O(\log n)$from sortedcontainers import SortedList class 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复杂度时间复杂度 $O(n\log n)$空间复杂度 $O(n)$。7.5 四大应用小结四个应用讲了两种构造有序序列的方式前缀和与插入排序。其中能力检测二分很常见本质只是把普通二分的 if 部分改造成了函数计数二分是能力检测二分的特例理论上单调栈/队列也是有序的也可以用来做二分但相关题目太少保持对有序序列的敏感度即可。另外有时候有序序列还会换一种形式出现二叉搜索树BST。大家都知道可以在 $O(\log n)$ 时间内完成 BST 查找这个查找过程本质也是二分——BST 的中序遍历恰好就是一个有序序列如果一个数比当前节点值小一定在左子树有序序列的左侧比当前节点值大一定在右子树有序序列的右侧。八、总结战略与战术本文主要讲了两部分内容基本概念与一个中心本篇核心解空间可以大但不可以小、序列有序可能隐藏、需要构造、极值第 k 大/第 k 小以及二分法的灵魂——折半难点在于什么条件、舍弃哪部分。两种类型与四大应用系列进阶最左、最右插入模板解决解空间已明确如何用代码求解能力检测、计数、前缀和、插入排序四大应用解决如何构造解空间。战略上要明确二分的本质是折半核心在于什么时候将哪一半折半战术上要保持对有序序列的敏感度。判断一个问题能否用二分解决关键在于检测一个值的时候是否可以排除解空间中的一半元素——比如前文反复提到的如果 x 不行那么解空间中所有小于等于 x 的值都不行。按题目难度划分简单题直接给一个有序序列让你找满足条件的位置顶多局部有序、一维变二维可参考 91/binary-search.md 中的扩展内容旋转数组、二维矩阵、寻找最值等中等题需要你自己构造有序序列前缀和、插入排序二分困难题二分与其他专题结合例如二分 DFS 搜索。仓库中还提供了配套的可视化资料脑图源文件、thinkings/binary-search-1.en.md 与 thinkings/binary-search-2.en.md 讲义、91/binary-search.md 讲义以及 problems/875.koko-eating-bananas.md、problems/Kth-Pair-Distance.md、problems/Triple-Inversion.md、problems/493.reverse-pairs.md 等题目详解可以结合这些资源逐题验证明确解空间 → 找到折半条件 → 套用最左/最右模板的完整链路。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考