当前位置:网站首页>二分(整数二分、实数二分)
二分(整数二分、实数二分)
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;
}
边栏推荐
- The solution that flutterweb browser cannot be rolled back after refreshing
- 在一台服务器上部署多个EasyCVR出现报错“Press any to exit”,如何解决?
- MySQL error reporting solution
- FlutterWeb瀏覽器刷新後無法回退的解决方案
- 编译原理——预测表C语言实现
- Interview shock 62: what are the precautions for group by?
- Automatic operation and maintenance sharp weapon ansible Foundation
- Xin'an Second Edition; Chapter 11 learning notes on the principle and application of network physical isolation technology
- Interview assault 63: how to remove duplication in MySQL?
- 趣-关于undefined的问题
猜你喜欢
基于STM32+华为云IOT设计的智能路灯
PySpark算子处理空间数据全解析(5): 如何在PySpark里面使用空间运算接口
What is the reason why the video cannot be played normally after the easycvr access device turns on the audio?
Distributed (consistency protocol) leader election (dotnext.net.cluster implements raft election)
2022年大厂Android面试题汇总(二)(含答案)
Getting started with pytest ----- test case rules
传统家装有落差,VR全景家装让你体验新房落成效果
Getting started with pytest ----- allow generate report
EasyCVR电子地图中设备播放器loading样式的居中对齐优化
Pourquoi Li shufu a - t - il construit son téléphone portable?
随机推荐
面试突击63:MySQL 中如何去重?
The shell generates JSON arrays and inserts them into the database
Virtual machine startup prompt probing EDD (edd=off to disable) error
Establishment of graphical monitoring grafana
Smart street lamp based on stm32+ Huawei cloud IOT design
FlutterWeb瀏覽器刷新後無法回退的解决方案
Vscode replaces commas, or specific characters with newlines
Alibaba brand data bank: introduction to the most complete data bank
Solution qui ne peut pas être retournée après la mise à jour du navigateur Web flutter
Solid principle
分布式(一致性协议)之领导人选举( DotNext.Net.Cluster 实现Raft 选举 )
Getting started with pytest ----- test case rules
Wordcloud colormap color set and custom colors
Alertmanager sends the alarm email and specifies it as the Alibaba mailbox of the company
How to submit data through post
Solrcloud related commands
BearPi-HM_ Nano development environment
SQL statement optimization, order by desc speed optimization
EasyCVR授权到期页面无法登录,该如何解决?
酷雷曼多种AI数字人形象,打造科技感VR虚拟展厅