当前位置:网站首页>二分(整数二分、实数二分)
二分(整数二分、实数二分)
2022-07-06 10:01:00 【Stellaris_L】
二、二分
单调序列或单调函数中的查找方式。(终止条件:l=r)
整数域二分
解析
- 注意终止边界、左右区间取舍。
(1)缩小范围:r=mid,l=mid+1,取中间值:mid=(l+r)>>1。
(2)缩小范围:l=mid,r=mid+r,取中间值:mid=(l+r+1)>>1。
第一种不会取到 r r r这个值,第二种不会取到 l l l。可以用来处理无解的情况。最初的二分区间从[1,n]扩大到[1,n+1]和[0,n],若最后二分终止在这个越界的下标上,则无解。
huangzh
- 右移运算向下取整,整数除法向零取整。
模板
例题
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int n,q,k;
int main(){
cin>>n>>q;
for(int i=0;i<n;i++)cin>>a[i];
while(q--){
int k;
cin>>k;
int l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
if(a[mid]>=k)r=mid;
else l=mid+1;
}
if(a[l]!=k)cout<<"-1 -1"<<endl;
else {
cout<<l<<" ";
l=0,r=n-1;
while(l<r){
int mid=l+r+1>>1;
if(a[mid]<=k)l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}
实数域二分
解析
- 注意精度问题
使用循环固定次数的二分方法解决精度问题。(精度比eps高)
模板
for(int i=0;i<100;i++){
//求mid
double mid=(l+r)/2;
if(calc(mid))r=mid; else l=mid;
}
例题
- eps的精度要求
#include <iostream>
using namespace std;
int main(){
double n;
cin>>n;
double l=-10000,r=10000;
while(r-l>1e-8){
double mid=(l+r)/2;
if(mid*mid*mid>=n)r=mid;
else l=mid;
}
printf("%.6lf",l);
return 0;
}
边栏推荐
- 基本磁盘与动态磁盘 RAID磁盘冗余阵列区分
- connection reset by peer
- Unity粒子特效系列-闪星星的宝箱
- Binary search strategy
- node の SQLite
- sql语句优化,order by desc速度优化
- Cool Lehman has a variety of AI digital human images to create a vr virtual exhibition hall with a sense of technology
- 开源与安全的“冰与火之歌”
- FlutterWeb浏览器刷新后无法回退的解决方案
- [getting started with MySQL] fourth, explore operators in MySQL with Kiko
猜你喜欢
分布式不来点网关都说不过去
偷窃他人漏洞报告变卖成副业,漏洞赏金平台出“内鬼”
中移动、蚂蚁、顺丰、兴盛优选技术专家,带你了解架构稳定性保障
Manifest of SAP ui5 framework json
EasyCVR平台通过接口编辑通道出现报错“ID不能为空”,是什么原因?
Concept and basic knowledge of network layering
F200——搭载基于模型设计的国产开源飞控系统无人机
Pytest learning ----- pytest confitest of interface automation test Py file details
scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
OliveTin能在网页上安全运行shell命令(上)
随机推荐
SQL statement optimization, order by desc speed optimization
李書福為何要親自掛帥造手機?
Sqoop I have everything you want
Xin'an Second Edition: Chapter 12 network security audit technology principle and application learning notes
10 advanced concepts that must be understood in learning SQL
Alertmanager sends the alarm email and specifies it as the Alibaba mailbox of the company
Selected technical experts from China Mobile, ant, SF, and Xingsheng will show you the guarantee of architecture stability
开源与安全的“冰与火之歌”
Debug xv6
微信小程序中给event对象传递数据
Kivy tutorial: support Chinese in Kivy to build cross platform applications (tutorial includes source code)
[translation] principle analysis of X Window Manager (I)
Guidelines for preparing for the 2022 soft exam information security engineer exam
adb常用命令
微信小程序获取手机号
基本磁盘与动态磁盘 RAID磁盘冗余阵列区分
基于STM32+华为云IOT设计的智能路灯
Kernel link script parsing
Xin'an Second Edition; Chapter 11 learning notes on the principle and application of network physical isolation technology
【Elastic】Elastic缺少xpack无法创建模板 unknown setting index.lifecycle.name index.lifecycle.rollover_alias