二分法 - wenzhoullq/leetcode GitHub Wiki
模板
二分题目的题眼为:大于等于X的最小值,小于等于x的最大值,大于等于x的最小值的下标最大值,小于等于x的最大值的下标最小值,当然也存在大于x的最大值(旋转数组找临界点);
二分一般有开区间,闭区间和半开半闭区间三种写法,如int[] nums = {1,2,3,4,5,6},开区间是指left = -1 ,right = nums.length,闭区间是指left = 0 ,right = nums.length - 1;这里仅讨论开区间写法,开区间的最大好处在于不用记忆mid + 1 或则 mid - 1;
int left = -1, right = nums.length ;
while(left + 1 < right){
int mid = (right - left)/2 + left ;
if(nums[mid] > target) left = mid;
else right = mid ;
}
return right;
如模板所示,left最后一定是停在target的左边,而right一定停在target上(如果target存在),因此是找到大于等于target的最小值;一般模板固定为这个模板,具体查找的值要求变化则是通过改变查找值和下标,或则改return
入门学习题
LCR 172. 统计目标成绩的出现次数
278. 第一个错误的版本
367. 有效的完全平方数
374. 猜数字大小
441. 排列硬币
744. 寻找比目标字母大的最小字母
最值
274. H 指数
275. H 指数 II
475. 供暖器
875. 爱吃香蕉的珂珂
1011. 在 D 天内送达包裹的能力
1283. 使结果不超过阈值的最小除数
1482. 制作 m 束花所需的最少天数
1838. 最高频元素的频数
1870. 准时到达的列车最小时速 double有坑
1898. 可移除字符的最大数目
2187. 完成旅途的最少时间
2226. 每个小孩最多能分到多少糖果
2563. 统计公平数对的数目
2861. 最大合金数
最大值最小化/最小值最大化
P2678 [NOIP2015 提高组] 跳石头
410. 分割数组的最大值
1552. 两球之间的磁力
1760. 袋子里最少数目的球
1802. 有界数组中指定下标处的最大值
2064. 分配给商店的最多商品的最小值
2439. 最小化数组中的最大值
2513. 最小化两个数组中的最大值
2517. 礼盒的最大甜蜜度
2528. 最大化城市的最小电量
2560. 打家劫舍 IV
2616. 最小化数对的最大差值
二分+BFS
图的二分尽量别用二分,很容易tle
旋转数组
剑指 Offer 11. 旋转数组的最小数字
153. 寻找旋转排序数组中的最小值
81. 搜索旋转排序数组 II
154. 寻找旋转排序数组中的最小值 II
面试题 10.03. 搜索旋转数组
邻域比较
4. 寻找两个正序数组的中位数
162. 寻找峰值
540. 有序数组中的单一元素
无明显特征的二分
611. 有效三角形的个数
878. 第 N 个神奇数字容斥
1414. 和为 K 的最少斐波那契数字数目
1488. 避免洪水泛滥
1818. 绝对差值和
2055. 蜡烛之间的盘子