1. § 模板介绍

   1. 迭代版模板
   2. 递归版模板
   3. mid 指针

2. § 模板运用

   1. 二分查找入门
   2. 二分查找基础
   3. 二分查找进阶
   4. 其它题目补充

§ 模板介绍

迭代版模板

二分查找模板之迭代版

递归版模板

二分查找模板之递归版

mid 指针

二分查找模板之mid指针探究

§ 模板运用

2022年3月25日，有新增学习模块诞生：学习计划广场→专项突破→二分查找，我打算和同学们一起在未来的日子里拿下二分查找模块的所有徽章：

学习计划	学习天数	题目难度
二分查找入门	12	简单16 中等7 困难0
二分查找基础	20	简单0 中等39 困难1
二分查找进阶	23	简单4 中等14 困难29

除了需要动态增删的集合需要使用有序集合（红黑树orAVL树）不方便用套用模板外，但凡数组的二分查找我全部用了模板六（蓝红二分法），部分题增加了模板一、模板二、模板四或模板四+模板五写法，以后也会陆续增加适合的模板的写法。

二分查找入门

题目	题解	方法
704. 二分查找	704. 蓝红二分法二分查找目标元素	二分查找
374. 猜数字大小	374. 蓝红二分法二分查找目标元素	二分查找
35. 搜索插入位置	35. 蓝红二分法搜索插入位置	二分查找
852. 山脉数组的峰顶索引	852. 蓝红二分法二分查找目标元素	二分查找
367. 有效的完全平方数	367. 构造区间进行二分查找	二分查找
1385. 两个数组间的距离值	1385. 模拟到二分一题三解	二分查找
69. x 的平方根	69. 构造区间进行二分查找	二分查找
744. 寻找比目标字母大的最小字母	744. 蓝红二分法二分查找目标元素	二分查找
278. 第一个错误的版本	278. 蓝红二分法二分查找目标元素	二分查找
34. 在排序数组中查找元素的第一个和最后一个位置	34. 蓝红二分法单模板秒杀二分查找	二分查找
441. 排列硬币	441. 构造区间进行二分查找	二分查找
1539. 第 k 个缺失的正整数	1539. 线性查找到二分查找	二分查找
167. 两数之和 II - 输入有序数组	167. 线性查找到二分查找	二分查找
1608. 特殊数组的特征值	1608. 蓝红二分法分左右	二分查找
1351. 统计有序矩阵中的负数	1351. 线性查找到二分查找	二分查找
74. 搜索二维矩阵	74. 线性查找到二分查找	二分查找
1337. 矩阵中战斗力最弱的 K 行	1337. 线性查找到二分查找	二分查找
1346. 检查整数及其两倍数是否存在	1346. 线性查找到二分查找	二分查找
350. 两个数组的交集 II	350. 逐步缩小二分查找区间	二分查找
633. 平方数之和	633. 二分查找找平方根	二分查找
1855. 下标对中的最大距离	1855. 逐步缩小二分查找区间	二分查找
33. 搜索旋转排序数组	33. 二分查找预处理转化为经典二分查找题	二分查找
153. 寻找旋转排序数组中的最小值	153. 蓝红二分法分左右	二分查找

二分查找基础

题目	题解	方法
209. 长度最小的子数组	209. 二分查找区间和	前缀和 + 二分查找
611. 有效三角形的个数	611. 蓝红二分法分左右	排序 + 二分查找
658. 找到 K 个最接近的元素	658. 抽象的蓝红划分方案详解	二分查找
1894. 找到需要补充粉笔的学生编号	1894. 模拟到二分	前缀和 + 二分查找
300. 最长递增子序列	300. 根据处理策略决定蓝红划分方案	动态规划 + 贪心 + 二分查找
1760. 袋子里最少数目的球	1760. 构造区间进行二分查找	二分查找
875. 爱吃香蕉的珂珂	875. 构造区间进行二分查找	二分查找
1552. 两球之间的磁力	1552. 构造区间进行二分查找	排序 + 二分查找
287. 寻找重复数	287. 元素范围映射下标范围常用解法	二分查找
1283. 使结果不超过阈值的最小除数	1283. 构造区间进行二分查找	二分查找
1898. 可移除字符的最大数目	1898. 蓝红二分法分左右	二分查找
1870. 准时到达的列车最小时速	1870. 构造区间进行二分查找	二分查找
1482. 制作 m 束花所需的最少天数	1482. 构造区间进行二分查找	二分查找
1818. 绝对差值和	1818. 明确查找目标转化为二分查找问题	排序 + 二分查找
240. 搜索二维矩阵 II	240. 逐步缩小二分查找区间	二分查找
275. H 指数 II	275. 蓝红二分法分左右	二分查找
1838. 最高频元素的频数	1838. 搜索区间常用解决方案	排序 + 前缀和 + 二分查找
540. 有序数组中的单一元素	540. 蓝红二分法分左右	二分查找
222. 完全二叉树的节点个数	222. 构造区间进行二分查找	位运算 + 二分查找
1712. 将数组分成三个子数组的方案数	1712. 多次利用二分查找加速线性查找	前缀和 + 二分查找
826. 安排工作以达到最大收益	826. 线性查找到二分查找	排序 + 二分查找
436. 寻找右区间	436. 蓝红二分法分左右	排序 + 二分查找
81. 搜索旋转排序数组 II	81. 二分查找预处理转化为经典二分查找题	二分查找
162. 寻找峰值	162. 深入理解二分查找	二分查找
154. 寻找旋转排序数组中的最小值 II	154. 蓝红二分法分左右	二分查找
528. 按权重随机选择	528. 构造区间进行二分查找	前缀和 + 二分查找
1574. 删除最短的子数组使剩余数组有序	1574. 全区间分三段后再搜索区间	双指针 + 二分查找
1508. 子数组和排序后的区间和	1508. 多次利用二分查找加速线性查找，官方题解优化	前缀和 + 二分查找
1292. 元素和小于等于阈值的正方形的最大边长	1292. 蓝红二分法分左右	前缀和 + 二分查找
1498. 满足条件的子序列数目	1498. 双指针 and 二分查找一题双解	排序 + 二分查找
981. 基于时间的键值存储	981. 蓝红二分法分左右	二分查找
1300. 转变数组后最接近目标值的数组和	1300. 多重二分查找 + 多维度二分查找，官方题解优化	排序 + 前缀和 + 二分查找
1802. 有界数组中指定下标处的最大值	1802. 构造区间进行二分查找	二分查找
1901. 找出顶峰元素 II	1901. 深入理解二分查找	二分查找
1146. 快照数组	1146. 模拟到二分	二分查找
1488. 避免洪水泛滥	1488. 雨天蓄水晴天放水最晚测涝最早防涝	贪心 + 二分查找
1562. 查找大小为 M 的最新分组	1562. 正向思维 vs 逆向思维	二分查找
1648. 销售价值减少的颜色球	1648. 多重二分查找 + 多维度二分查找	排序 + 前缀和 + 二分查找
1201. 丑数 III	1201. 蓝红二分法分左右	二分查找
911. 在线选举	911. 蓝红二分法分左右	二分查找

二分查找进阶

题目	题解	方法
1213. 三个有序数组的交集	1213. 蓝红二分法二分查找目标元素	二分查找
1099. 小于 K 的两数之和	1099. 线性查找到二分查找	排序 + 二分查找
1150. 检查一个数是否在数组中占绝大多数	1150. 线性查找到二分查找	二分查找
1428. 至少有一个 1 的最左端列	1428. 蓝红二分法分左右	二分查找
702. 搜索长度未知的有序数组	702. 倍增扩大二分缩小	二分查找
1011. 在 D 天内送达包裹的能力	1011. 构造区间进行二分查找	二分查找
1533. 找到最大整数的索引	1533. 闭区间分割区间	二分查找
1060. 有序数组中的缺失元素	1060. 线性查找到二分查找	二分查找
270. 最接近的二叉搜索树值	270. 蓝红二分法双指针夹逼	二分查找
1231. 分享巧克力	1231. 构造区间进行二分查找	二分查找
1891. 割绳子	1891. 构造区间进行二分查找	二分查找
1885. 统计数对	1885. 二分查找 and 双指针一题双解	排序 + 二分查找
1618. 找出适应屏幕的最大字号	1618. 蓝红二分法分左右	二分查找
793. 阶乘函数后 K 个零	793. 构造区间进行二分查找	二分查找
1198. 找出所有行中最小公共元素	1198. 蓝红二分法二分查找目标元素	二分查找
668. 乘法表中第k小的数	668. 蓝红二分法分左右	二分查找
719. 找出第 k 小的距离对	719. 多次利用二分查找加速线性查找	排序 + 差分 + 前缀和 + 二分查找 / 排序 + 二分查找 + 滑动窗口
1751. 最多可以参加的会议数目 II	1751. 蓝红二分法分左右	排序 + 动态规划 + 二分查找
1671. 得到山形数组的最少删除次数	1671. 线性查找到二分查找	贪心 + 动态规划 + 二分查找
786. 第 K 个最小的素数分数	786. 实数集上的蓝红二分法	二分查找
1182. 与目标颜色间的最短距离	1182. 蓝红二分法双指针夹逼	二分查找
1793. 好子数组的最大分数	1793. 以下标k为分界线分转化两个数组问题	二分查找
1095. 山脉数组中查找目标值	1095. 多次二分查找	二分查找
4. 寻找两个正序数组的中位数	4. 多重二分查找 + 多维度二分查找	二分查找
1235. 规划兼职工作	1235. 线性查找到二分查找	排序 + 动态规划 + 二分查找
1713. 得到子序列的最少操作次数	1713. 转化为最长递增子序列问题	贪心 + 二分查找
1439. 有序矩阵中的第 k 个最小数组和	1439. 蓝红二分法分左右	深度优先搜索 / 广度优先搜索 + 二分查找
1847. 最近的房间	1847. 离线查询 and 在线查询 + 二分查找	排序 + 二分查找 / 树状数组 + 二分查找
363. 矩形区域不超过 K 的最大数值和	363. 借助有序集合进行二分查找	前缀和 + 二分查找
1862. 向下取整数对和	1862. 逐步缩小二分查找区间	排序 + 滑动窗口 + 二分查找
644. 子数组最大平均数 II	644. 构造区间进行二分查找	前缀和 + 滑动窗口 + 二分查找
1889. 装包裹的最小浪费空间	1889. 线性查找到二分查找	排序 + 前缀和 + 二分查找
710. 黑名单中的随机数	710. 第 k 个缺失的非负整数	排序 + 二分查找
352. 将数据流变为多个不相交区间	352. 借助有序集合进行二分查找	二分查找
778. 水位上升的泳池中游泳	778. 模拟到二分，官方题解优化	深度优先搜索 / 广度优先搜索 + 二分查找
378. 有序矩阵中第 K 小的元素	378. 蓝红二分法分左右	二分查找
774. 最小化去加油站的最大距离	774. 构造区间进行二分查找	二分查找
1187. 使数组严格递增	1187. 模拟最长递增子序列	动态规划 + 贪心 + 二分查找
1062. 最长重复子串	1062. 蓝红二分法分左右	字符串哈希 + 二分查找
1044. 最长重复子串	1044. 蓝红二分法分左右	字符串哈希 + 二分查找
718. 最长重复子数组	718. 蓝红二分法分左右	字符串哈希 + 二分查找
887. 鸡蛋掉落	887. 蓝红二分法二分查找目标元素	动态规划 + 二分查找
1521. 找到最接近目标值的函数值	1521. 蓝红二分法双指针夹逼	位运算 + 线段树 + 二分查找
1157. 子数组中占绝大多数的元素	1157. 二分查找上下界	排序 + 哈希表 + 二分查找 / 线段树 + 哈希表 + 二分查找
302. 包含全部黑色像素的最小矩形	302. 蓝红二分法分左右	二分查找
1631. 最小体力消耗路径	1631. 蓝红二分法分左右	深度优先搜索 / 广度优先搜索 + 二分查找
1782. 统计点对的数目	1782. 二分查找 and 双指针一题双解	排序 + 二分查找
部分题目写题解比较难讲清楚思路，我正在努力绘制图片讲解，争取图文并茂帮助你理解，如果感觉题解比较简陋请见谅，可以留言或者私信提出意见或者建议，也欢迎各位同学和我进行技术交流！

2022年5月16日，跟着学习计划走的同学应该已经把二分查找的全部三枚徽章收入囊中了，相信你对二分查找的理解已经非常透彻了！

其它题目补充

题目	题解	方法
259. 较小的三数之和	259. 二分查找 and 双指针	排序 + 二分查找
354. 俄罗斯套娃信封问题	354. 转化为最长递增子序列问题	排序 + 贪心 + 动态规划 + 二分查找
362. 敲击计数器	362. 数组 or 有序集合 and 二分查找	二分查找
713. 乘积小于K的子数组	713. 乘法转加法，二分查找区间和	前缀和 + 二分查找
1918. 第 K 小的子数组和	1918. 多重二分查找 + 多维度二分查找	前缀和 + 二分查找
剑指 Offer 11. 旋转数组的最小数字	剑指 Offer 11. 蓝红二分法分左右	二分查找
剑指 Offer 53 - II. 0～n-1中缺失的数字	剑指 Offer 53 - II. 蓝红二分法分左右	二分查找

这些题目没有被收录在学习计划广场的二分查找专题训练中，截止至2022年5月16日，总计有100题左右，有空我都用蓝红二分法写一遍。

同学们对哪个模板特别有偏爱或者有其他更好的二分查找模板都可以留言或者私信。

此贴不定期维护更新。