当前位置:网站首页>二分(整数二分、实数二分)
二分(整数二分、实数二分)
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;
}
边栏推荐
- Quick start of Hongmeng system
- Automatic operation and maintenance sharp weapon ansible Playbook
- Awk command exercise
- [introduction to MySQL] third, common data types in MySQL
- FlutterWeb浏览器刷新后无法回退的解决方案
- BearPi-HM_ Nano development board "flower protector" case
- 面试突击62:group by 有哪些注意事项?
- 传统家装有落差,VR全景家装让你体验新房落成效果
- The solution that flutterweb browser cannot be rolled back after refreshing
- Pourquoi Li shufu a - t - il construit son téléphone portable?
猜你喜欢
78 岁华科教授逐梦 40 载,国产数据库达梦冲刺 IPO
Easy introduction to SQL (1): addition, deletion, modification and simple query
趣-关于undefined的问题
基本磁盘与动态磁盘 RAID磁盘冗余阵列区分
Pourquoi Li shufu a - t - il construit son téléphone portable?
[introduction to MySQL] third, common data types in MySQL
[introduction to MySQL] the first sentence · first time in the "database" Mainland
面试突击62:group by 有哪些注意事项?
EasyCVR电子地图中设备播放器loading样式的居中对齐优化
Unity小技巧 - 绘制瞄准准心
随机推荐
Smart street lamp based on stm32+ Huawei cloud IOT design
Pyspark operator processing spatial data full parsing (4): let's talk about spatial operations first
Interview assault 63: how to remove duplication in MySQL?
Getting started with pytest ----- test case pre post, firmware
Quick start of Hongmeng system
Yarn: unable to load file d:\programfiles\nodejs\yarn PS1, because running scripts is prohibited on this system
微信小程序中给event对象传递数据
Unity粒子特效系列-闪星星的宝箱
Alibaba brand data bank: introduction to the most complete data bank
Distinguish between basic disk and dynamic disk RAID disk redundant array
Growth of operation and maintenance Xiaobai - week 7
Summary of Android interview questions of Dachang in 2022 (I) (including answers)
scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
面试突击62:group by 有哪些注意事项?
Grafana 9 is officially released, which is easier to use and more cool!
Mysqlimport imports data files into the database
Nodejs developer roadmap 2022 zero foundation Learning Guide
The easycvr authorization expiration page cannot be logged in. How to solve it?
《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
There is a gap in traditional home decoration. VR panoramic home decoration allows you to experience the completion effect of your new house