二分写法总结

#二分写法总结| 来源: 网络整理| 查看: 265

文章目录写在前面整数二分二分查找二分答案二分求上界二分求下界浮点数二分

写在前面

首先二分的思想不难，问题在于整数二分的时候如果没有处理好二分的区间，会导致死循环的情况，比如下面这种二分求上界的写法

int binarySearch(int l, int r) { while(l while(l while(l + 1 =2 { int mid = (l + r) / 2; if(check(mid)) l = mid; //检查mid是否符合题目要求 else r = mid; } return l; }

循环结束后区间大小就是1，即 [l, l+1)，最终答案就是l 但是这样的写法需要注意以下3点：

初始二分的潜在的答案区间的右端点r要设置成比最大可能答案大，因为r不会被访问到还是 l + r 可能溢出如果题目说了可能没有答案，最后需要检查下 l，因为可能二分的区间里没有答案，每次循环都是 r = mid，最终的l没有被检查过二分求下界

当我们设置二分潜在的答案区间为左开右闭的时候，即 (l, r]，最终得到的 r 就是答案的下界，因为这时候 r 的左侧答案都已经不符合要求，r必定是答案中最小的了

int lowerBound(int l, int r) { while(l + 1 =2 { int mid = (l + r) / 2; if(check(mid)) r = mid; //检查mid是否符合题目要求 else l = mid; } return r; }

同样的我们也需要注意以下三点：

初始二分的潜在的答案区间的左端点l要设置成比最小可能答案大小，因为l不会被访问到还是 l + r 可能溢出如果题目说了可能没有答案，最后需要检查下 r，因为可能二分的区间里没有答案，每次循环都是 l = mid，最终的r没有被检查过浮点数二分

浮点数二分基本不会有什么问题，因为不会有整数二分取整没取好导致死循环的问题

有两种写法：

以循环次数为循环终止条件

for(int i = 0; i mid = (l + r) / 2; //检查mid }

比较推荐第一种写法，因为第二种如果精度设置过小，加上浮点数的精度问题还是可能死循环

【本文地址】

二分写法总结

二分写法总结

今日新闻

推荐新闻