分享丨【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小）
By 灵茶山艾府
图: 闭区间二分循环结束时的左右指针位置（查找第一个 8）
题目已按照难度分排序，右侧数字为难度分。
如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。
二分查找
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 35. 搜索插入位置
- 704. 二分查找
- 744. 寻找比目标字母大的最小字母
- 2529. 正整数和负整数的最大计数
- 2300. 咒语和药水的成功对数 1477
- 2389. 和有限的最长子序列 (排序 + 前缀和 + 二分)
- 1170. 比较字符串最小字母出现频次 (统计后 排序 + 二分)
- 2080. 区间内查询数字的频率 1702 (哈希预处理, 二分LR索引差)
- 2563. 统计公平数对的数目 1721 (排序后 二分LR索引差)
- 2856. 删除数对后的最小数组长度 1750 (
[!]数学证明后贪心: 求在有序数组中出现次数最多的元素的数量) - 981. 基于时间的键值存储 (哈希套红黑树)
- 1146. 快照数组 1771
- 1818. 绝对差值和 1934
- 911. 在线选举 2001 (被我写复杂了...写了个懒删除堆预处理...)
- LCP 08. 剧情触发时间 (前缀和 + 二分)
- 1150. 检查一个数是否在数组中占绝大多数（会员题）
- 1064. 不动点（会员题）
- 702. 搜索长度未知的有序数组（会员题）
- 1182. 与目标颜色间的最短距离（会员题）
- 2819. 购买巧克力后的最小相对损失（会员题）
- 2936. 包含相等值数字块的数量（会员题）
二分答案: 求最小
- 1283. 使结果不超过阈值的最小除数 1542 (
check函数) - 2187. 完成旅途的最少时间 1641 (
check函数) - 1870. 准时到达的列车最小时速 1676 (
check函数, 避免浮点运算的小技巧: 如果题目明确最多只有几位小数, 那么我们可以所有相关的先乘以 , 然后再恢复.) - 1011. 在 D 天内送达包裹的能力 1725 (
check函数) - 875. 爱吃香蕉的珂珂 1766 (
check函数) - 475. 供暖器
- 1385. 两个数组间的距离值
- 2594. 修车的最少时间 1915
- 1482. 制作 m 束花所需的最少天数 1946
- 3048. 标记所有下标的最早秒数 I 2263
- 3049. 标记所有下标的最早秒数 II 3111
- 2604. 吃掉所有谷子的最短时间（会员题）
- 2702. 使数字变为非正数的最小操作次数（会员题）
二分答案: 求最大
在练习时，请注意「求最小」和「求最大」的二分写法上的区别。
前面的「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）。
「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别。
以开区间二分为例：
- 求最小：
check(mid) == true时更新right = mid，反之更新left = mid，最后返回right。 - 求最大：
check(mid) == true时更新left = mid，反之更新right = mid，最后返回left。
对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其它二分写法，开区间写法不需要思考加一减一等细节，个人推荐使用开区间写二分。
- 275. H 指数 II
- 2226. 每个小孩最多能分到多少糖果 1646
- 1898. 可移除字符的最大数目 1913
- 1802. 有界数组中指定下标处的最大值 1929 (二分 + 贪心)
- 1642. 可以到达的最远建筑 1962 (可以用贪心+优先队列)
- 2861. 最大合金数 1981
- 3007. 价值和小于等于 K 的最大数字 2258 (位运算 | 数位dp | 试填法 | 数学)
- 2141. 同时运行 N 台电脑的最长时间 2265
- 2258. 逃离火灾 2347
- 2071. 你可以安排的最多任务数目 2648
- 1618. 找出适应屏幕的最大字号（会员题）
- 1891. 割绳子（会员题）
- 2137. 通过倒水操作让所有的水桶所含水量相等（会员题）
- 644. 子数组最大平均数 II（会员题）
二分答案: 计算间接结果
- 3143. 正方形中的最多点数 ~1600
最小化最大值
本质是二分答案求最小。
- 410. 分割数组的最大值 (学习啦~)
- 2064. 分配给商店的最多商品的最小值 1886
- 1760. 袋子里最少数目的球 1940
- 1631. 最小体力消耗路径 1948
- 2439. 最小化数组中的最大值 1965
- 2560. 打家劫舍 IV 2081
- 778. 水位上升的泳池中游泳 2097 相当于最小化路径最大值 (二分 + dfs)
- 2616. 最小化数对的最大差值 2155 (排序后二分配对)
- 2513. 最小化两个数组中的最大值 2302
- 774. 最小化去加油站的最大距离（会员题）
最大化最小值
本质是二分答案求最大。
- 2517. 礼盒的最大甜蜜度 2021
- 1552. 两球之间的磁力 同 2517 题
- 2812. 找出最安全路径 2154 (多源BFS + 并查集)
- 2528. 最大化城市的最小供电站数目 2236
- LCP 12. 小张刷题计划
- 1102. 得分最高的路径（会员题）
- 1231. 分享巧克力（会员题）
第 K 小/大
部分题目也可以用堆解决。
- 378. 有序矩阵中第 K 小的元素 -> 前置题目: 240. 搜索二维矩阵 II
- 668. 乘法表中第 K 小的数
- 373. 查找和最小的 K 对数字 (堆 / 多路归并 / 二分(复杂))
- 719. 找出第 K 小的数对距离
- 878. 第 N 个神奇数字 1897 (lcm + 容斥原理)
- 1201. 丑数 III 2039 (lcm + 容斥原理)
- 793. 阶乘函数后 K 个零 2100
- 1439. 有序矩阵中的第 k 个最小数组和 2134
- 786. 第 K 个最小的素数分数 2169
- 3116. 单面值组合的第 K 小金额 2387
- 3134. 找出唯一性数组的中位数 ~2400
- 2040. 两个有序数组的第 K 小乘积 2518
- 2386. 找出数组的第 K 大和 2648
- 1508. 子数组和排序后的区间和 思考：二分做法
- 1918. 第 K 小的子数组和（会员题）
其它
- 2476. 二叉搜索树最近节点查询 (二叉搜索树的中序遍历是有序数组, 然后二分)
- 74. 搜索二维矩阵
- 240. 搜索二维矩阵 II
- 278. 第一个错误的版本
- 374. 猜数字大小
- 162. 寻找峰值
- 1901. 寻找峰值 II (二分难想)
- 852. 山脉数组的峰顶索引
- 1095. 山脉数组中查找目标值 1827 (三次二分)
- 153. 寻找旋转排序数组中的最小值 (有技巧的二分)
- 33. 搜索旋转排序数组 (超级有技巧的二分)
- 1539. 第 k 个缺失的正整数
- 540. 有序数组中的单一元素
- 4. 寻找两个正序数组的中位数 (有点难)
- 1060. 有序数组中的缺失元素（会员题）
- 1198. 找出所有行中最小公共元素（会员题）
- 1428. 至少有一个 1 的最左端列（会员题）
- 1533. 找到最大整数的索引（会员题）
- 2387. 行排序矩阵的中位数（会员题）
