二分搜索与快速排序.ppt

《二分搜索与快速排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二分搜索与快速排序快速排序（QuickSort）思想：每一轮选取1个基准数X，把大于X的元素放在X右边，小于X的元素放在X左边，此时序列被划分为X左边的子序列和X右边的子序列，分别对两个子序列再进行相同的操作，直到整个序列有序。void quick_sort(int s[], int l, int r){if (l < r){//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1int i = l, j = r, x = s[l];while (i < j){while(i < j && s[j] >= x) //从右向左找第一个小于x的数

2、j--;if(i < j)s[i++] = s[j];while(i < j && s[i] < x) //从左向右找第一个大于等于x的数i++;if(i < j)s[j--] = s[i];}s[i] = x;quick_sort(s, l, i - 1); //递归调用quick_sort(s, i + 1, r);}}重要应用：查找第k大元素利用快速排序的思想，我们可以在平均复杂度O(n)的时间复杂度内求出一个序列的第K大元素。思想：对于每一轮基准数归位后，可以根据要查找元素跟基准数的相对位置在对应子序列中进行查找。二分搜索简单定义在一个单调有序的集合中查找元素，每次将集合分为左右

3、两部分，判断解在那个部分并调整上下界，重复直到找到目标元素。时间复杂度：O(logn),优于直接顺序查找O(n)intBsearch(intarray[],intlow,inthigh,inttarget){while(low<=high){intmid=(low+high)/2;if(array[mid]>target)high=mid-1;elseif(array[mid]

4、rget的下标，这样使用效果不理想，能不能求出值等于target的完整区间呢（由于已经排好序，相等的值会排在一起）？所以一般用二分查找求下界或上界求下界：找到有序数组a1,a2,...,an中第一个大于等于k的元素的位置low=1;high=n;while(high-low>1)//不断缩小答案区间(low,high]{mid=(low+high)>>1;if(a[mid]>=k)high=mid;elselow=mid;}cout<

5、Upper_bound(first,last,val)算法返回非递减序列[first,last)中第一个大于val的位置#includesort(a+1,a+n+1);pos=lower_bound(a+1,a+n+1,x)-a;重要模型：这个算法除了在有序数列查找值外，在求最优解的问题上非常有用。若有一个“求满足某个条件C（x）的最小的x”问题，如果所有的x’>=x也满足C(x’)的话，就可以用二分查找来解决。首先我们将区间的左端点初始化为不满足C(x)的值，右端点初始化为满足C(x)的值。然后每次取中点mid=(low+high)/2，判断C（mid）是否满足并

6、缩小范围，直到（low,high],足够小了为止。最后high就是要求的最小值。最大化的问题也可以用同样的方法求解，请自行思考。这样便把最优化问题转化为可行性问题。这种算法也叫作“二分答案”。满足这样性质的问题典型的有“最大值最小化”、“最小值最大化”HOJ2651PIE题目大意：有f+1个人分n块披萨，每个人要求分得的面积一样，且披萨只能被切开而不能重新组合，求每个人能分到的最大面积。注意在输出小数的问题中，一般都会指定允许的误差范围，在二分时设置合理的精度。循环终止条件可设为像(ub-lb)>EPS这样，如果EPS太小，就有可能会因为浮点小数精度的原因导致死循环。POJ2456agg

7、ressivecows题目大意：农夫约翰搭了一间有N间牛舍的小屋。牛舍排在一条线上，第i号牛舍在xi的位置。但是他的M头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。分析：“最小值最大化”问题，使用前面总结的模型。C(d):=可以安排牛的位置使得最近的两头牛的距离不小于d=可以安排牛的位置使得任意两头牛的间距都不小于dvoidsol