深圳建设培训中心网站,中国徐州网,手机网站建设实验报告,网站首页改版方案文章目录 二分一、整数二分#xff08;一#xff09;整数二分思路#xff08;二#xff09;整数二分算法模板1.左查找#xff08;寻找左侧边界#xff09;2.右查找#xff08;寻找右侧边界#xff09;3.总模板 #xff08;三#xff09;题目#xff1a;数的范围 二、… 文章目录 二分一、整数二分一整数二分思路二整数二分算法模板1.左查找寻找左侧边界2.右查找寻找右侧边界3.总模板 三题目数的范围 二、浮点数二分一浮点数二分思路二浮点数二分算法模板三题目数的三次方根 二分
一、整数二分
一整数二分思路 二整数二分算法模板 1.左查找寻找左侧边界
查找的情况分为三种 当a[mid]2时rmid-1l不变当a[mid]2时lmid1r不变当a[mid]2时如果我们一找到就返回那么返回的结果将会是下标4此时并不是目标值
因此我们需要向左缩小区间 向左缩小区间就是令rmidl不变此时区间变为[0,4],既保证了下标为4的2保留在区间里又保证可以继续查找[0,4]中是否还有数字2如果[0,3]中没有数字2了则下标4就会是该区间唯一一个满足条件的值也就会是最终结果。而如果[0,3]中还有其他的2就如本例那么下标为4的数字就会被下一次缩小区间所抛弃。 这里模拟一下样例 最后l r退出循环。此时如果r就是最终结果那么l同时也是最终结果。另一种退出循环的方式就是lrl跑到r的右边那么不管怎么说l都不可能是最终目标。因此最后只用判断r是否是最终目标就好了。 判断r是否是x如果退出循环后a[r]x说明找到了x并且这个x是左边界的x如果a[r]!x说明连x都找不到返回-1 结果如下
void query_l(int a)
{int l0,rn-1;while(lr){int mid(lr)/2;if(arr[mid]a) rmid;else if(arr[mid]a) rmid-1;else lmid1;}if(arr[l]a) coutr ;else cout-1 ;
}我们可以将等于和大于的情况合二为一因为不管怎样最终都是要判断r是否为目标值的。所以升级后的代码如下。
void query_l(int a)
{int l0,rn-1;while(lr){int mid(lr)/2;if(arr[mid]a) rmid;else lmid1;}if(arr[l]a) coutr ;else cout-1 ;
}2.右查找寻找右侧边界
右查找就是要找到最后出现的值不断向右缩小区间。分析过程与左查找类似。需要注意的一点右查找和左查找确定mid值的方式不同。左查找采用lr/2向下取整的方式右查找采用lr1/2向上取整的方式。原因分析对于左查找假设l2r3向下取整得到的mid(231)/23若取rmid那么l和r任保持原值不变陷入死循环。对于右查找假设l2r3向下取整得到mid(23)/22。若取lmid那么l和r任保持原值不变陷入死循环。
void query_r(int a)
{int l0,rn-1;while(lr){int mid(lr1)/2;if(arr[mid]a) lmid;else rmid-1;}if(arr[r]a) coutr;else cout-1;
}3.总模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid 1, r]时使用
int bsearch_1(int l, int r)
{while (l r){int mid l r 1;if (check(mid)) r mid; // check()判断mid是否满足性质else l mid 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
int bsearch_2(int l, int r)
{while (l r){int mid l r 1 1;if (check(mid)) l mid;else r mid - 1;}return l;
}三题目数的范围
给定一个按照升序排列的长度为 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
输入样例
6 3
1 2 2 3 3 4
3
4
5输出样例
3 4
5 5
-1 -1#includeiostream
using namespace std;
const int N 100010;int n,m;
int q[N];int main()
{scanf(%d %d,n,m);for(int i0;in;i)scanf(%d,q[i]);while(m--){int x;scanf(%d,x);int l0,rn-1;while(lr){int mid(lr)/2;if(q[mid]x)rmid;else lmid1;}if(q[l]!x)cout-1 -1endl;else{coutl ;int l0,rn-1;while(lr){int mid(lr1)/2;if(q[mid]x)lmid;elsermid-1;}coutlendl;}}return 0;
}二、浮点数二分
一浮点数二分思路
思路和整数二分一样区别是浮点型二分不需要注意边界问题也就是不需要1
二浮点数二分算法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r)
{const double eps 1e-6; // eps 表示精度取决于题目对精度的要求while (r - l eps){double mid (l r) / 2;if (check(mid)) r mid;else l mid;}return l;
}三题目数的三次方根
题目描述
给定一个浮点数n求它的三次方根。
输入格式 共一行包含一个浮点数n。
输出格式 共一行包含一个浮点数表示问题的解。
注意结果保留6位小数。
数据范围 −10000≤n≤10000
输入样例
1000.00输出样例
10.000000#includeiostream
using namespace std;
int main()
{double x;cinx;double l-100,r100;//根据题目范围 开三次方根 估计答案大概范围while(r-l1e-8){double mid(lr)/2;if(mid*mid*midx)rmid;elselmid;}printf(%.6lf\n,l);return 0;
}
