栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【二分总结模板】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【二分总结模板】

实习的几个月,和java毫无相关,刷的题都要忘了,隔离期间重新回顾下,再次回看大雪菜的二分。

自己总结下,方便以后自己复习

这里二分分为两个模板,把自己找个条件,让这段数呈现一个二分性,然后找mid,如果mid在找的条件的这个点

1、

        如果mid在绿颜色部分,也就是我们要找的条件点在mid左侧,同时mid也有可能是这个条件点,那么我们就要往左边继续筛选,筛选范围就要由【L,R】变为【L,M】;

        如果mid在红颜色部分,也就是我们要找的条件点在mid的右侧,我们继续往右边筛选,筛选范围就要由【L,R】变为【mid+1,R】

2、

        如果mid在红颜色部分,也就是我们要找的条件点在mid右侧,同时mid也有可能是这个条件点,那么我们就要往右边继续筛选,筛选范围由【L,R】变为【mid,R】

        如果mid在绿颜色部分,也就是我们要找的条件点在mid左侧,我们继续往左边筛选,筛选范围就要由【L,R】变为【L,mid-1】

因此 也可以直接根据自己写出的一个条件来判断是模板几,来完善后面的代码。

这里以 【367. 有效的完全平方数】 为例来走一遍此二分流程。

1、首先二分边界。int left = 0,right=num;

2、while(left < right){

                long mid = left + right >> 1;

                if() 

        }        

 3、这里设计的check函数条件为:mid * mid > num,注意这里用 mid * mid,而 int 类型有限,故采用 long 类型。

4、然后思考下,如果mid * mid < num,说明 条件点 还在 mid 右侧,且mid也有可能是,继续往右边筛选,则变L,不变R,即【L,R】 --->【mid,R】;如果mid * mid > num,说明条件点在 mid 左侧,往左边筛选,则L不变,变 R 即【L,R】 ---> 【L,mid-1】

5、补充代码

        while(left < right){

                        long mid = left + right >> 1;

                        if(mid * mid < num)  left = mid;

                        else if (mid * mid > num) right = mid -1;

                } 

              

所以 left + right +1 >> 2;

完成代码为:

模板一、模板二写法均可。 

 

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970061.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号