网硕互联帮助中心特点：找数+二段性
时间复杂度O(logN)
本质：只要有二段性就可以用二分，而非仅局限于有序
比如D.二分查找－二分答案－求最小——3639. 变为活跃状态的最小时间和D.二分查找－二分答案－求最大——1898. 可移除字符的最大数目就未必有序，但存在二段性（可以理解为单调性），一样可以二分
思维导图概览
👉处理边界思路模板来源
二分查找
以下两种模型中，目标位置设为target，循环结束时left和right指向同一位置
如果target为确定值，则left和right会停在t1位置
否则left和right会停在t2位置
mid在最左端点的左边、mid在最右端点的右边的条件要自己分析着写
注：最左端点模型和最右端点模型针对整型二分，浮点二分直接mid=(left+right)/2即可
求最左端点模型
①目标位置：第一个大于等于target的位置
②mid靠左：int mid=left+(right-left)/2;
③if(mid在最左端点的左边) 让最左端点的左边往里靠，还要超过：
if(s[mid]<t) left=mid+1;
else 另一边靠过来就行：right=mid;
④返回值：left和right均可（因为会重合）
求最右端点模型
①目标位置：最后一个小于等于target的位置
②mid靠右：int mid=left+(right-left+1)/2;
③if(mid在最右端点的右边) 让最右端点的右边往里靠，还要超过：
if(s[mid]<t) right=mid-1;
else 另一边靠过来就行：left=mid;
④返回值：left和right均可（因为会重合）
模型使用步骤
①问题是否具有二段性
②确定目标值是否是个确定值，根据问题选择模型
③确定left和right共同指向的最终位置
④最终位置不符题意时进行边界处理调整，原理参考👇
D.二分查找-进阶——1170. 比较字符串最小字母出现频次
基础
题目已给排序
题目及解析👇
优选算法-二分：18.在排序数组中查找元素的第一个和最后一个位置
优选算法-二分：19.搜索插入位置
优选算法-二分：17.二分查找
D.二分查找-基础——744. 寻找比目标字母大的最小字母
D.二分查找-基础-2529. 正整数和负整数的最大计数
进阶
部分题目需要先排序，然后在有序数组上二分查找
题目及解析👇
D.二分查找-进阶——2300. 咒语和药水的成功对数
D.二分查找-进阶——1385. 两个数组间的距离值
D.二分查找-进阶——2389. 和有限的最长子序列
D.二分查找-进阶——1170. 比较字符串最小字母出现频次
D.二分查找-进阶——2080.区间内查询数字的频率
D.二分查找-进阶——3488. 距离最小相等元素查询
D.二分查找-进阶——981. 基于时间的键值存储
D.二分查找-进阶——658. 找到 K 个最接近的元素
D.二分查找-进阶——1287. 有序数组中出现次数超过25%的元素
D.二分查找-进阶——2476. 二叉搜索树最近节点查询
二分答案
在此题型中我们只需要关注三个东西：两个变量+一个逻辑👇
①目标条件：题目要求达到的变量
②目标变量：调节目标条件的变量，也是我们需要二分的变量
③转换逻辑：目标变量通过转换逻辑与目标条件联系起来
目标条件随着目标变量单调变化，可以是正相关也可以是负相关
check方法就是转换逻辑的体现，具体返回值取决于怎么定义
(1)如果符合目标条件返回true，对应二分模型中就是mid不动（最左端点模型right=mid、最右端点模型left=mid），比如👇
D.二分查找－二分答案－求最大——1898. 可移除字符的最大数目
D.二分查找－二分答案－求最大——1802. 有界数组中指定下标处的最大值
(2)如果要顺着二分的调整来，那么就正好跟(1)相反，对应二分模型中就是mid向里靠（最左端点模型left=mid+1、最右端点模型right=mid-1）
下方我的博客题解一开始大多是(2)的写法，顺着二分模型调整而返回的，自1898题开始时(1)的写法，大家一开始理解方便可以采用(1)的写法，也可以对比理解
正相关的题目比如👇
D.二分查找－二分答案－求最小——2187.完成旅途的最少时间
D.二分查找－二分答案－求最小——3296. 移山所需的最少秒数
第 175 场双周赛Q2——3824. 减小数组使其满足条件的最小 K 值
D.二分查找－二分答案－求最小——3639. 变为活跃状态的最小时间
D.二分查找－二分答案－求最小——475. 供暖器
A.每日一题——3453. 分割正方形 I(拿最左端点分析，越大越符合条件，就是正相关单调)
D.二分查找－二分答案－求最大——1898. 可移除字符的最大数目
D.二分查找－二分答案－最小化最大值——2560. 打家劫舍 IV
D.二分查找－二分答案－最小化最大值——LCP 12. 小张刷题计划
D.二分查找－二分答案－第K小/第K大——668. 乘法表中第k小的数（模板题）
D.二分查找－二分答案－第K小/第K大——378. 有序矩阵中第 K 小的元素
D.二分查找－二分答案－第K小/第K大——719. 找出第 K 小的数对距离
D.二分查找－二分答案－第K小/第K大——878. 第 N 个神奇数字
D.二分查找－二分答案－第K小/第K大——1201. 丑数 III
D.二分查找－二分答案－第K小/第K大——793. 阶乘函数后 K 个零
负相关的题目比如👇
D.二分查找-二分答案-求最小——1283. 使结果不超过阈值的最小除数（模板题）
D.二分查找－二分答案－求最小——1011. 在 D 天内送达包裹的能力
D.二分查找－二分答案－求最小——875. 爱吃香蕉的珂珂
D.二分查找－二分答案－求最小——1870. 准时到达的列车最小时速
D.二分查找－二分答案——275. H 指数 II
D.二分查找－二分答案－求最大——2226. 每个小孩最多能分到多少糖果
D.二分查找－二分答案－求最大——2982. 找出出现至少三次的最长特殊子字符串 II
D.二分查找－二分答案－求最大——1802. 有界数组中指定下标处的最大值
D.二分查找－二分答案－求最大——3143. 正方形中的最多点数
D.二分查找－二分答案－最小化最大值——410. 分割数组的最大值（模板题）
D.二分查找－二分答案－最小化最大值——2064. 分配给商店的最多商品的最小值
D.二分查找－二分答案－最小化最大值——1760. 袋子里最少数目的球
D.二分查找－二分答案－最小化最大值——2439. 最小化数组中的最大值
D.二分查找－二分答案－最大化最小值——3281. 范围内整数的最大得分（模板题）
D.二分查找－二分答案－最大化最小值——2517. 礼盒的最大甜蜜度
D.二分查找－二分答案－最大化最小值——1552. 两球之间的磁力
求最小
在此题型中，通常采用最左端点模型找最小（也叫第一个符合的）
题目及解析👇
D.二分查找－二分答案－求最小——278. 第一个错误的版本（模板题）
D.二分查找-二分答案-求最小——1283. 使结果不超过阈值的最小除数
D.二分查找－二分答案－求最小——2187.完成旅途的最少时间
D.二分查找－二分答案－求最小——1011. 在 D 天内送达包裹的能力
D.二分查找－二分答案－求最小——875. 爱吃香蕉的珂珂
D.二分查找－二分答案－求最小——3296. 移山所需的最少秒数
第 175 场双周赛Q2——3824. 减小数组使其满足条件的最小 K 值
D.二分查找－二分答案－求最小——3639. 变为活跃状态的最小时间
D.二分查找－二分答案－求最小——475. 供暖器
D.二分查找－二分答案－求最小——1870. 准时到达的列车最小时速
A.每日一题——3453. 分割正方形 I
D.二分查找－二分答案——275. H 指数 II
求最大
在此题型中，通常采用最右端点模型找最大（也叫最后一个符合的）
题目及其解析👇
D.二分查找－二分答案——275. H 指数 II
D.二分查找－二分答案－求最大——2226. 每个小孩最多能分到多少糖果
D.二分查找－二分答案－求最大——2982. 找出出现至少三次的最长特殊子字符串 II
D.二分查找－二分答案－求最大——2576. 求出最多标记下标
D.二分查找－二分答案－求最大——1898. 可移除字符的最大数目
D.二分查找－二分答案－求最大——1802. 有界数组中指定下标处的最大值
D.二分查找－二分答案－求最大——3143. 正方形中的最多点数
最小化最大值
本质：求最小
题目及解析👇
D.二分查找－二分答案－最小化最大值——410. 分割数组的最大值（模板题）
D.二分查找－二分答案－最小化最大值——2064. 分配给商店的最多商品的最小值
D.二分查找－二分答案－最小化最大值——1760. 袋子里最少数目的球
D.二分查找－二分答案－最小化最大值——2439. 最小化数组中的最大值
D.二分查找－二分答案－最小化最大值——2560. 打家劫舍 IV
D.二分查找－二分答案－最小化最大值——LCP 12. 小张刷题计划
最大化最小值
本质：求最大
题目及解析👇
D.二分查找－二分答案－最大化最小值——3281. 范围内整数的最大得分（模板题）
D.二分查找－二分答案－最大化最小值——2517. 礼盒的最大甜蜜度
D.二分查找－二分答案－最大化最小值——1552. 两球之间的磁力
第K小/第K大
第K小/第K大问题转换方法：（注意以下是至少≠恰好）
第K小=求最小的x，满足≤x的数至少K个
第K大=求最大的x，满足≥x的数至少K个
解释为啥不是恰好：因为满足至少时，说明当前mid一定符合条件，缩小范围时会缩小到mid处，而mid一定合法，只有不符合时才会越过mid去寻找合法的，并且也顺带着解决了元素相同的问题，因此要用至少
题目及解析👇
D.二分查找－二分答案－第K小/第K大——668. 乘法表中第k小的数（模板题）
D.二分查找－二分答案－第K小/第K大——378. 有序矩阵中第 K 小的元素
D.二分查找－二分答案－第K小/第K大——719. 找出第 K 小的数对距离
D.二分查找－二分答案－第K小/第K大——878. 第 N 个神奇数字
D.二分查找－二分答案－第K小/第K大——1201. 丑数 III
D.二分查找－二分答案－第K小/第K大——793. 阶乘函数后 K 个零
其他
题目及解析👇
优选算法-二分：20.x的平方根
优选算法-二分：21.山峰数组的峰顶
优选算法-二分：22.寻找峰值
优选算法-二分：23.搜索旋转排序数组中的最小值
优选算法-二分：24.0~n-1中缺失的数字
D.二分查找－二分答案－其他——74. 搜索二维矩阵
D.二分查找－二分答案－其他——374. 猜数字大小
D.二分查找－二分答案－其他——540. 有序数组中的单一元素+LCR 070. 有序数组中的单一元素
D.二分查找－二分答案－其他——1539. 第 k 个缺失的正整数
评论前必须登录！
注册