《二分搜索与快速排序.ppt》由会员分享，可在线阅读，更多相关《二分搜索与快速排序.ppt（16页珍藏版）》请在三一文库上搜索。
1、二分搜索与快速排序,快速排序（Quick Sort）,思想：每一轮选取1个基准数X，把大于X的元素放在X右边，小于X的元素放在X左边，此时序列被划分为X左边的子序列和X右边的子序列，分别对两个子序列再进行相同的操作，直到整个序列有序。,voidquick_sort(ints,intl,intr)if(l=x)/从右向左找第一个小于x的数j-;if(ij)si+=sj;,while(ij,重要应用：查找第k大元素,利用快速排序的思想，我们可以在平均复杂度O(n)的时间复杂度内求出一个序列的第K大元素。思想：对于每一轮基准数归位后，可以根据要查找元素跟基准数的相对位置在对应子序列中进行查找。,二分
2、搜索 简单定义,在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在那个部分并调整上下界，重复直到找到目标元素。时间复杂度：O(logn),优于直接顺序查找O(n),int Bsearch(int array, int low, int high, int target) while(low target) high = mid - 1; else if (arraymid target) low = mid + 1; else return mid; /找到目标数,返回它的下标 return -1;/没有找到目标数,二分查找求下界或上界,但若数组中有多个元素都是target，它
3、只会返回中间那一个target的下标，这样使用效果不理想，能不能求出值等于target的完整区间呢（由于已经排好序，相等的值会排在一起）？所以一般用二分查找求下界或上界,求下界：找到有序数组a1,a2,.,an中第一个大于等于k的元素的位置,low=1; high=n; while (high-low1) /不断缩小答案区间(low,high mid=(low+high) 1; if (amid=k) high=mid; else low=mid; couthighendl;,STL,Lower_bound(first, last, val) 算法返回非递减序列 first, last) 中第
4、一个大于等于val的位置Upper_bound(first, last, val) 算法返回非递减序列 first, last) 中第一个大于val的位置,#include sort(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）是
5、否满足并缩小范围，直到（low,high,足够小了为止。最后high就是要求的最小值。最大化的问题也可以用同样的方法求解，请自行思考。这样便把最优化问题转化为可行性问题。这种算法也叫作“二分答案”。满足这样性质的问题典型的有“最大值最小化”、“最小值最大化”,HOJ 2651 PIE,题目大意：有f + 1个人分n块披萨，每个人要求分得的面积一样，且披萨只能被切开而不能重新组合，求每个人能分到的最大面积。,注意,在输出小数的问题中，一般都会指定允许的误差范围，在二分时设置合理的精度。循环终止条件可设为像(ub - lb) EPS 这样，如果EPS太小，就有可能会因为浮点小数精度的原因导致死循环
6、。,POJ 2456 aggressive cows,题目大意：农夫约翰搭了一间有N间牛舍的小屋。牛舍排在一条线上，第i号牛舍在xi的位置。但是他的M头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。,分析：“最小值最大化”问题，使用前面总结的模型。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),三分法,当需要求某凸形或凹形函数的极值，通过函数本身表达式并不容易求解，就可以用三分法不断逼近求解。,1、当 f(mid) f(mmid) 的时候，我们可以断定 mmid 一定在白点的右边。反证法：假设 mmid 在白点的左边，则 mid 也一定在白点的左边，又由f(mid) f(mmid) 可推出mmid mmid，与已知矛盾，故假设不成立。同理，此时可以将 L = mid 来缩小范围。,