二分法

二分法

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式 第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式 共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围 1≤n≤100000 1≤q≤10000 1≤k≤10000

#include<bits/stdc++.h> using namespace std; #define N 100005 int A[N],n,p,x; int Binear_search(int x,int l,int h) { while(l<h) { int mid=(l+h+1)>>1; if(A[mid]<=x) l=mid; else h=mid-1; } return l; } int Binear_search1(int x,int l,int h) { while(l<h) { int mid=(l+h)>>1; if(A[mid]>=x) h=mid; else l=mid+1; } return h; } int main(){ freopen("in.txt","r",stdin); scanf("%d %d",&n,&p); for(int i=0;i<n;i++) scanf("%d",&A[i]); for(int j=0;j<p;j++) { scanf("%d",&x); int a=Binear_search(x,0,n-1); int b=Binear_search1(x,0,n-1); if(A[a]==x&&A[b]==x) { printf("%d %d\n",b,a); } else printf("-1 -1\n"); } return 0; }

注意：

mid的赋值要放在while函数以内；要想输出规范，可以把输入数据放在文件中，直接读取就可；

三次方根

给定一个浮点数n，求它的三次方根。

输入格式 共一行，包含一个浮点数n。

输出格式 共一行，包含一个浮点数，表示问题的解。

注意，结果保留6位小数。

数据范围 −10000≤n≤10000

#include<bits/stdc++.h> using namespace std; const double eps=1e-8; double n; double bsearch(double l,double h){ while(h-l>eps){ double mid=(l+h)/2; if(mid*mid*mid<=n) l=mid; else h=mid; } return l; } int main(){ scanf("%lf",&n); printf("%f\n",bsearch(-100,100)); return 0; } /* scanf("%f",&n);运行出错 scanf("%lf",&n);运行正确 */

注意：

定义误差范围时往往选取比要求输出的格式大10^-2;由于是double类型，所以h=mid,而不是h=mid+1; 为成功学会二分法干杯