二分查找..ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,CUGB ACM/ICPC GROUP,CUGB ACM/ICPC GROUP,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,CUGB ACM/ICPC GROUP,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,CUGB ACM/ICPC GROUP,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,CUGB ACM/ICPC GROUP,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选课件,*,二分查找算法,简单定义：在一个,单调有序,的集合中查找元素，每次将,集合,分为左右两部分，判断解在哪个部分中并调整,集合,上下界，重复直到找到目标元素。,时间复杂度：O(logn)，优于直接顺序查找O(n),二分查找算法,例子,：,/x：待查找的元素，n：数组集合大小，num数组,单调递增,int low=0,high=n,mid,res=-1;/low:,集合,下界 high：,集合,上节,while(low=high),mid=(low+high)/2;/mid:将,集合,分割为两部分,if(nummid=x)/查找到符合元素x,res=mid;,break;,else if(nummid 1.0e-6),mid=(high+low)/2;,if(Caculate(mid)=4时v的最大值即可得,到答案,/由于精度差问题，考虑先将面积*1000000转化为整数来二分,long long res,mid;,while(low=high),mid=(high+low)/2;,if(judge(mid),low=mid+1;,res=mid;/最后结果为res,else,high=mid-1;,核心代码,bool judge(long long mid),long long p=0;,for(int i=0;i=f;,推荐题目,Poj 3273 ,1434,Hdu 2141,2899,1969,Coj 1080,1216,1048,当需要求某凸性或凹形函数的极值，通过函数本身表达式并不容易求解时，就可以用三分法不断逼近求解。,三分法,类似二分的定义Left和Right,mid=(Left+Right)/2,midmid=(mid+Right)/2;,如果mid靠近极值点，则Right=midmid；,否则(即midmid靠近极值点)，则Left=mid;,三分法,例子：ZOJ 3203 Light Bulb,mid,midmid;,while(low+eps cmidmid),high=midmid;,else,low=mid;,核心代码,double cal(double,x,),return(h*D-H*x)/(D-x)+x;,/,这里放要求的函数；,对于求解一些实际问题，当公式难以推导出来时，二分、三分法可以较为精确地求解出一些临界值，且效率也是令人满意的。,灵活应用这些方法对解题会很有帮助。,总结,