河南省建设厅网站103号文件,报价网站,电子商务类网站模板,婚礼婚庆网站建设需求分析一、二分搜索
1、查找数的范围
原题链接 这道题看似是二分搜索的题目#xff0c;实则就是二分搜索。与一般的搜索不同的是#xff0c;若查找元素重复#xff0c;则分别返回重复元素的左端下标和右端下标#xff0c;若不存在则返回“-1 -1。我们常用的二分搜索是返回的…一、二分搜索
1、查找数的范围
原题链接 这道题看似是二分搜索的题目实则就是二分搜索。与一般的搜索不同的是若查找元素重复则分别返回重复元素的左端下标和右端下标若不存在则返回“-1 -1。我们常用的二分搜索是返回的重复元素的左端下标稍作修改则可以返回右端元素下标。
#includeiostream
#includestdio.h
using namespace std;
const int N 1e510;
int a[N];//若存在重复元素则返回左边界
int searchLeft(int q[],int l,int r,int x)
{while(lr){int mid lr1;if(q[mid]x){l mid1;}else{r mid ;}}return l;
}
//若存在重复则返回右边界
int searchRight(int q[],int l,int r,int x)
{while(lr){int mid (lr1)1;if(q[mid]x)l mid;elser mid-1;}return r;
}
int main()
{int n,m;cinnm;for(int i0;in;i){cina[i];}while(m--){int num;cinnum;//搜索左边界int pos1 searchLeft(a,0,n-1,num);//搜索有边界if (a[pos1]!num){cout-1 -1endl;}else{int pos2 searchRight(a,0,n-1,num);coutpos1 pos2endl;}}system(pause);return 0;
}2、数的三次方根
原题链接 这道题可以用二分搜索的方法来搜索一个数的三次方根的近似解。
#includeiostream
using namespace std;
int main()
{double x,l -100000.0,r 100000.0;cinx;while(r-l1e-8){double mid (lr)/2.0;if(mid*mid*mid x){l mid;}elser mid;}printf(%.6f\n,r);return 0;
}
