二分查找
发布日期:2021-06-29 11:10:21
浏览次数:2
分类:技术文章
本文共 3079 字,大约阅读时间需要 10 分钟。
使用二分查找的前提;所查找的部分一定要具有单调性;
二分查找的理论; 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较, 如果x=a[n/2]则找到x,算法终止。 如果x《a[n/2],则我们只要在数组a的左半部继续搜索x,这里假设数组元素呈升序排列)。 如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。1;二分查找之数组;
已知一个数组利用二分查找找到某个元素的下标;#includeint ef(int*a,int len, int t)//查找的函数{ int st = 0; int end = len-1; int mid ; **while(st <= end){ //跳出循环的条件 mid = (end -st)/2+st;//防止 (end +st)越界 if(a[mid] == t){ //这个if结构是关键 return mid; } else if(a[mid] > t){ end = mid-1; } else st = mid+1; }** return -1;//没有找到这个元素}int main(){ int m; int a[10]={ 1,2,3,4,5,6,7,8,9,10}; m = ef(a,10,8);//在数组a[10]中找元素8的位置; printf("%d\n",m); return 0 ;}
2;对函数二分查找;
就是解方程,保证精确度; HDOJ-2199 给出方程: 8*x4 + 7*x3 + 2*x2 + 3*x + 6 = Y 其中,实数Y满足 (fabs(Y) <= 1e10) 输入Y 请输出x在区间[0,100]的解,结果精确到小数点后4位。#includedouble f(double x){ double y; y = 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6; return y;}int main(){ int n; double y,st,end, mid; scanf("%d",&n); while(n--){ scanf("%lf",&y); if(f(0)<=y&&y<=f(100)){ st = 0; end = 100; while(end - st > 1e-7){ //1e-7是精度问题; mid = (end-st)/2+st; if(f(mid) > y){ end = mid-1e-7; } else st = mid + 1e-7; } printf("%.4lf\n",(end-st)/2+st); } else printf("No solution!\n"); } return 0 ;}
上面的1e-7次是保证精确度问题,一般取1e-7就好了;
3;二分查找对方程的导数二分查找;
HDOJ-2899 给出函数: F(x) = 6*x7 + 8*x6 + 7*x3 + 5*x2 - y*x 其中,实数y满足 (0#include#include double y;double ds(double x)//导函数是单调递增的函数; { return 42.0*pow(x,6.0)+48.0*pow(x,5.0)+21.0*pow(x,2.0)+10.0*x-y;} double hs(double x){ return 6.0*pow(x,7.0)+8.0*pow(x,6.0)+7.0*pow(x,3.0)+5.0*pow(x,2.0)-y*x;}int main(){ int n; double st,end,mid; scanf("%d",&n); while(n--){ scanf("%lf",&y); if(ds(100)<0){ //导数的最大值都小于0则他就是最小值了 printf("%.4lf\n",hs(100)); continue; } if(ds(0)>0){ printf("%.4lf\n",hs(0)); continue; } st = 0; end = 100; while(end-st>1e-8){ //这里的精度是????? mid = (end-st)/2+st; if(ds(mid)<0){ //导数小于0则说明最小值在中间到后面那部分 st = mid; } else{ end = mid; } } printf("%.4lf\n",hs(mid)); } return 0 ;}
4;
4.1二分查找使用的关键在于; 被查找的一定要具有单调性; 4.2二分查找代码实现的关键在于 while条件和if判断与折中;while(end-st>1e-8){ //保证精确度一般取1e-7左右; mid = (end-st)/2+st; if(ds(mid)<0){ //导数小于0则说明最小值在中间到后面那部分 st = mid; } else{ end = mid; } }
while(end - st > 1e-7){ //1e-7是精度问题; mid = (end-st)/2+st; if(f(mid) > y){ end = mid-1e-7; } else st = mid + 1e-7; }
看几个样例应该有点感觉了吧;
转载地址:https://blog.csdn.net/zw1996/article/details/51878307 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月17日 22时55分20秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
光立方,永远的神!
2019-04-29
学习STM32很简单?
2019-04-29
电赛 | 电源题软件如何准备?
2019-04-29
手把手教你DIY一款属于自己的万能红外遥控器!
2019-04-29
速看 | 电子元器件如何确定好坏?
2019-04-29
485通信自动收发电路,历史上最详细的解释
2019-04-29
【视觉盛宴三】不好意思,这些线材接口的横截面真的没见过
2019-04-29
一位头发发白的神人教你怎么写程序,运维,买电脑,写文章,平面设计!
2019-04-29
【第二期】那些设计漂亮、有创意的电路板!
2019-04-29
【第三期】那些设计漂亮、有创意的电路板!
2019-04-29
继续推荐公众号~
2019-04-29
「第二篇」全国一等奖,经验帖。
2019-04-29
「第三篇」全国电子设计竞赛,这些你必须知道的比赛细节,文末附上近十年电赛题目下载...
2019-04-29
5G小科普(漫画版,So easy!)
2019-04-29
无人再提华强北
2019-04-29
千万不要小瞧那些不好好写代码的程序员
2019-04-29
80后,天才程序员, Facebook 第一任 CTO,看看开挂的人生到底有多变态?
2019-04-29
「第四篇」电赛控制题可以准备一些什么?
2019-04-29
「第五篇」全国电子设计竞赛-电源题设计方案总结
2019-04-29
「第六篇」对于电赛,我们应该看重什么?
2019-04-29