淘客手机端网站建设,wordpress 分类伪静态,广州做网站网络公司,网站推广怎么做的在基本算法中#xff0c;二分法的应用非常广泛#xff0c;它是一种思路简单、编程容易、效率极高的算法。蓝桥杯软件类大赛中需要应用二分法的题目很常见。
二分法有整数二分和实数二分两种应用场景
二分法的概念
二分法的概念很简单#xff0c;每次把搜索范围缩小为上一…在基本算法中二分法的应用非常广泛它是一种思路简单、编程容易、效率极高的算法。蓝桥杯软件类大赛中需要应用二分法的题目很常见。
二分法有整数二分和实数二分两种应用场景
二分法的概念
二分法的概念很简单每次把搜索范围缩小为上一次的1/2直到找到答案为止。
二分法的效率很高只需计算log(n)次。
下面介绍二分法的模板代码bin_search()函数
我们用猜数字的例子先给数组初始化然后定义你要猜的数用二分法效率高。
对于二分法的讲解非常细致都在注释中。
#includebits/stdc.h
using namespace std;
int a[1000];
int bin_search(int *a, int n, int x) { //在数组a中查找数字x返回位置int left 0, right n; //left 通常初始化为 0表示搜索范围的左边界是数组的第一个元素right通常初始化为 n数组的长度表示搜索范围的右边界是数组的最后一个元素的下一个位置。while (left right) {int mid left(right-left)/2; //mid的标准写法建议这样写不能用(leftright)/2,有可能会整数溢出的。 if (a[mid] x) right mid; //x小在左边把右边的一半砍掉这里就不用加1了我们本身就是大于等于x。 else left mid1; //加1的原因是我们要跳过 a[mid] 这个元素因为它小于 x我们要的是等于x的元素 couta[mid] ; //输出猜数的过程 如果你想省略过程可以注释掉这一行的输出语句。 }return left; //返回left所在的索引不要牵扯到right避免混淆right一开始是索引的下一个位置。
}
int main() {int n 100;for(int i0; in; i) a[i]i1; //赋值数字1100int test 54; //猜54这个数int pos bin_search(a,n,test);cout\ntesta[pos];
}
bin_search()有3个重要点区间左端点left、区间右端点right、二分的中位数mid。每次把区间缩小一半把left或right移动到mid直到left right为止即找到答案所处的位置。 二分法的作用
二分法可以把一个长度为n的有序序列上O(n)的查找时间优化到O(logn)。
注意应用二分法的前提序列是有序的按从小到大或从大到小排序。 无序的序列无法二分如果是无序的序列则应该先排序再对其进行二分先排序再二分排序的复杂度是O(nlog2(n))二分的复杂度是O(log2(n))。排序加二分的总复杂度是O(nlog2(n))。如果使用暴力法直接在无序的n个数里面查找最多查找n次复杂度是O(n)的比先排序再二分快。如果不是查找一个数而是查找m个数那么先排序再做m次二分的计算复杂度是O(nlog2(n) mlog2(n))而暴力法的复杂度是O(mn)此时二分法远好于暴力法。 整数二分
在单调递增序列中查找x或者x的后继
前面介绍的bin_search()函数就是“在单调递增序列中查找x或者x的后继”的模板代码。
二分函数都是一摸一样的测试数据可以改一下看看能不能查找后继
int main() {int n 100;for(int i0; in; i) a[i]2*i2; //赋值数字2200偶数int test 55; //查找55或55的后继int pos bin_search(a,n,test);couttesta[pos];//56 55没有只能找56了。
} 在单调递增序列中查找x或者x的前驱
#includebits/stdc.h
using namespace std;
int a[1000];
int bin_search2(int *a, int n, int x) {int left 0, right n;while (left right) {int mid left (right-left 1)/2 ; //1是为了确保在 left 和 right 之间的元素数量是奇数时mid 会指向中间元素当元素数量是偶数时mid 会指向中间两个元素的右侧那个元素。//这样做的原因是我们希望在存在重复元素时mid 尽可能向右偏移从而找到最右侧的那个等于或小于 x 的元素。if (a[mid] x) left mid;else right mid - 1;}return left;
}
int main() {int n 100;for(int i0; in; i) a[i]2*i2; //赋值数字2200,偶数int test 55; //查找55或55的前驱int pos bin_search2(a,n,test);couttesta[pos]; //54
}
整数二分例题
例题1.分巧克力
2017年第八届省赛lanqiaoOJ题号99 先试试暴力法从边长为1开始到最大边长d每个值都试一遍一直试到刚好够分的最大边长为止。编程思路边长初始值d 1然后d 2、3、4……一个一个地试 。
代码
#includebits/stdc.h
using namespace std;
int h[100010],w[100010];//多申请10个空间
int n,k;
bool check(int d) { //检查够不够分int num0;for(int i0; in; i) num (h[i]/d)*(w[i]/d);//假如将6×5的巧克力的长边6个单位和宽边5个单位分别除以2×2的小正方形的边长2个单位。//这样可以得到长边可以切出3个2×2的巧克力宽边可以切出2个2×2的巧克力。//接着将长边和宽边切出的巧克力块数相乘即3长边切出的块数× 2宽边切出的块数 6。所以一块6×5的巧克力可以切出6块2×2的巧克力。if(numk) return true; //够分else return false; //不够分
}
int main() {cin nk;for(int i0; in; i) cinh[i]w[i]; //长宽各自存在各自的数组中 int d1; //正方形边长while(1) {if(check(d)) d; //边长从1开始一个一个地试else break;}cout d-1;return 0; //暴力求解只能过75的测试数据 最后两个测试数据错了暂时不知道什么原因
}
整数二分法求解
#includebits/stdc.h
using namespace std;
int n,k;
const int N100010;
int h[N],w[N];
bool check(int d) {int num0;for(int i0; in; i) num (h[i]/d)*(w[i]/d);if(numk) return true; //够分else return false; //不够分
}
int main() {cin n k;for(int i0; in; i) cinh[i]w[i];int L1, RN; //R的初值是100010//第一种写法while(LR) {int mid(LR1) / 2; //除以2向右取整 不会整数溢出直接LRif(check(mid)) Lmid; //新的搜索区间是右半部分R不变调整Lmidelse Rmid-1; //新的搜索区间是左半部分L不变调整Rmid–1}cout L;//第二种写法/* while(LR) {int mid(LR) / 2; //除以2向左取整 不会整数溢出直接LRif(check(mid)) Lmid1; //新的搜索区间是右半部分R不变更新Lmid1else Rmid; //新的搜索区间是左半部分L不变更新Rmid}cout L-1; */return 0;
} 实数二分
与整数二分相比实数二分的编程就容易多了不用考虑整数的取整问题。实数二分的模板代码如下。
const double eps 1e-7; //精度。
while(right - left eps) { double mid left(right-left)/2;if (check(mid)) right mid; //判定然后继续二分check(mid)为true执行此语句else left mid;
}
