二分搜索与快速排序.ppt

,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,二分搜索与快速排序,1,快速排序（,Quick Sort,）,思想：每一轮选取,1,个基准数,X,，把大于,X,的元素放在,X,右边，小于,X,的元素放在,X,左边，此时序列被划分为,X,左边的子序列和,X,右边的子序列，分别对两个子序列再进行相同的操作，直到整个序列有序。,2,voidquick_sort(ints,intl,intr),if(lr),/Swap(sl,s(l+r)/2);/,将中间的这个数和第一个数交换参见注,1,inti=l,j=r,x=sl;,while(ij),while(i=x)/,从右向左找第一个小于,x,的数,j-;,if(ij),si+=sj;,while(ij&six)/,从左向右找第一个大于等于,x,的数,i+;,if(ij),sj-=si;,si=x;,quick_sort(s,l,i-1);/,递归调用,quick_sort(s,i+1,r);,3,重要应用：查找第,k,大元素,利用快速排序的思想，我们可以在平均复杂度,O(n),的时间复杂度内求出一个序列的第,K,大元素。,思想：对于每一轮基准数归位后，可以根据要查找元素跟基准数的相对位置在对应子序列中进行查找。,4,二分搜索 简单定义,在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在那个部分并调整上下界，重复直到找到目标元素。,时间复杂度：,O(logn),优于直接顺序查找,O(n),5,int Bsearch(int array,int low,int high,int target),while(low target),high=mid-1;,else if(arraymid 1)/,不断缩小答案区间,(low,high,mid=(low+high)1;,if(amid=k),high=mid;,else,low=mid;,couthigh=x,也满足,C(x),的话，就可以用二分查找来解决。首先我们将区间的左端点初始化为不满足,C(x),的值，右端点初始化为满足,C(x),的值。然后每次取中点,mid=(low+high)/2,，判断,C,（,mid,）是否满足并缩小范围，直到（,low,high,足够小了为止。最后,high,就是要求的最小值。,最大化的问题也可以用同样的方法求解，请自行思考。,这样便把最优化问题转化为可行性问题。这种算法也叫作“二分答案”。,满足这样性质的问题典型的有“最大值最小化”、“最小值最大化”,10,HOJ 2651 PIE,题目大意：有,f+1,个人分,n,块披萨，每个人要求分得的面积一样，且披萨只能被切开而不能重新组合，求每个人能分到的最大面积。,11,注意,在输出小数的问题中，一般都会指定允许的误差范围，在二分时设置合理的精度。,循环终止条件可设为像,(ub-lb)EPS,这样，如果,EPS,太小，就有可能会因为浮点小数精度的原因导致死循环。,12,POJ 2456 aggressive cows,题目大意：农夫约翰搭了一间有,N,间牛舍的小屋。牛舍排在一条线上，第,i,号牛舍在,xi,的位置。但是他的,M,头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。,13,分析：“最小值最大化”问题，使用前面总结的模型。,C(d):=,可以安排牛的位置使得最近的两头牛的距离不小于,d,=,可以安排牛的位置使得任意两头牛的间距都不小于,d,void solve()/,二分答案部分,int low=0;high=INF;,while(high-low1),int mid=(low+high)1;,if(C(mid)low=mid;,else high=mid;,printf(%dn,lb),14,三分法,当需要求某凸形或凹形函数的极值，通过函数本身表达式,并不容易求解，就可以用三分法不断逼近求解。,15,1,、当,f(mid)f(mmid),的时候，我们可以断定,mmid,一定在白点的右边。,反证法：假设,mmid,在白点的左边，则,mid,也一定在白点的左边，又由,f(mid)f(mmid),可推出,mmid mid,，与已知矛盾，故假设不成立。,所以，此时可以将,R=mmid,来缩小范围。,2,、当,f(mid)f(mmid),的时候，我们可以断定,mid,一定在白点的左边。,反证法：假设,mid,在白点的右边，则,mmid,也一定在白点的右边，又由,f(mid)mmid,，与已知矛盾，故假设不成立。,同理，此时可以将,L=mid,来缩小范围。,16,