//二分有整数二分和浮点数二分 //二者有不同的模板 //首先来看看整数的二分 //当找的是区间右边界,用mode1 int mode1(int l,int r)//模板1区间[l,r]被划分为[l,mid]和[mid+1,r]使用 { //当然下面的循环也可以改成循环100次,2的100次方足够大,让我们找出答案 while(l>1;//开始二分 if(judge(mid)) r=mid;//judge是自己定义的函数,假如judge出来的数大于期望的,说明期望的数在右边,则得缩小范围 else l=mid+1;//否则在期望的数在左边,继续缩小 //这里说明一下 假如r=mid,则l一定得为mid+1,目的防止越界 return l;//返回期望值 } //当找的是区间左边界,用mode2 int mode2(int l,int r)//模板2区间[l,r]被划分为[l,mid-1]和[mid,r]使用 { //当然下面的循环也可以改成循环100次,2的100次方足够大,让我们找出答案 while(l >1;//开始二分,l+r+1不能写成l+r,不然会死循环 if(judge(mid)) l=mid;//judge是自己定义的函数,假如judge出来的数小于期望的,说明期望的数在左边边,则得缩小范围 else r=mid-1;//否则在期望的数在右边,继续缩小 //这里说明一下 假如l=mid,则r一定得为mid-1,目的防止越界 } return l;//返回期望值 } //再看看浮点数二分 //浮点数就没那么多讲究了 double mode(double l,double r) { //当然下面的循环也可以改成循环100次,2的100次方足够大,让我们找出答案 while(r-l>1e-8)//看题目要求精确到几位小数,加入两位,则是1e-4,都比要求要多2 { double mid=l+r>>1;//开始二分 if(judge(mid)) r=mid;//judge是自己定义的函数,假如judge出来的数大于期望的,说明期望的数在右边,则得缩小范围 else l=mid;//否则在期望的数在左边,继续缩小 //这里不用考虑+1或者-1的情况,因为浮点型除法是准确的 } return l;//返回期望值 }
789. 数的范围 - AcWing题库https://www.acwing.com/problem/content/791/
下面来看列子
#includeusing namespace std; const int N=1e6+10; int a[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i >1; if(a[mid]>=x) r=mid; else l=mid+1; } if(a[l]!=x) printf("-1 -1n"); else { printf("%d ",l);//输出左边界 l=0,r=n-1; while(l >1; if(a[mid]<=x) l=mid; else r=mid-1; } printf("%dn",l);//输出右边界 } } return 0; }
790. 数的三次方根 - AcWing题库https://www.acwing.com/problem/content/792/下面给出浮点代码
#includeusing namespace std; int main() { double n; scanf("%lf",&n); double l=-10000,r=10000; while(r-l>1e-8)//题目要求精确到6位小数则这里条件则得写6+2=8位 { double mid=(l+r)/2; if(mid*mid*mid>n) r=mid;//mid*mid*mid>n是judge条件 else l=mid; } printf("%.6lfn",l); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)