《二分查找及其应用ppt课件》由会员分享，可在线阅读，更多相关《二分查找及其应用ppt课件（21页珍藏版）》请在金锄头文库上搜索。
1、二分查找及其应用 By ElemenT今天，你今天，你ACAC了吗？了吗？NO!YES!请在这里输入您的标题刷题太无聊？我们玩游戏吧！相信大家都玩相信大家都玩过猜数字的猜数字的游游戏。两人游。两人游戏，A同学在心同学在心里默念一个整数里默念一个整数n（1 = n = 1000）。）。B同学猜同学猜n是多少。是多少。同同时如果如果B没有猜没有猜对，A告告诉他他这个数比默念的数高了个数比默念的数高了还是低了。是低了。最坏情况下，最坏情况下，ElemenTElemenT也也不不用用超超过过十十次次可以猜出！可以猜出！最坏情况下需要多少次呢？看起来好厉害的样子其其实并不是，下面将引入并不是，下面将引入
2、“二二分搜索分搜索”的概念。的概念。如上述的游如上述的游戏中，第一次中，第一次应该取多少呢？取多少呢？500！很不巧并不是很不巧并不是500，而是一个比，而是一个比500大的数。大的数。虽然运气不好，但是然运气不好，但是B将区将区间的的范范围砍掉了一半！砍掉了一半！那么下一次那么下一次B该猜什么。猜什么。大家已经发现，问题变成了501-1000之间猜一个数，那么应该猜(501+1000)/2 = 750!如果运气还是不好，又猜小了.没关系！只猜了仅仅两次，我们就将区间缩小为 751-1000.那么继续下去.我们发现，每次可以将区间缩小为原来的一半。递减速度显然就是log级别的。log(1000
3、)向上取整只有10.那么我们一定可以在10次之内猜出这个数。给定一个有序序列a0,a1,a2.aN，给出一个目标值tg，在序列中查找是否存在tg，如果存在，返回tg的下标。如何快速查找？我们必须看到数列是有序的充分利用有序的条件，充分利用有序的条件，类似猜似猜数一数一样查找找tg。复复杂度度为log(n)。那么我那么我们来看看如何来看看如何实现二分二分查找。找。int bs(int *a, int n, int tg) int l = 0, r = n-1; while(l tg) r = mid-1; else l = mid+1; return -1;二分查找的应用（二分答案）假定一个解判
4、断是否可行假定一个解判断是否可行最大化最小最大化最小值最大化平均最大化平均值有N条绳子，它们长度分别为Li。如果从他们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？答案保留两位小数。1=N=104, 1=K=104, 1=Li n k; for(int i = 0; i ai; double l = 0, r = 100001; for(int i = 0; i 100; i+) double m = (l+r)/2; if(ok(m) l = m; else r = m; printf(%.2fn, 0.01 * (int)(l*100) ); return 0;int n,
5、k;double amaxn, tot = 0;bool ok(double x) int num = 0; for(int i = 0; i = k) return true; return false;再看一道最大化最小值的例题这类问题通过二分搜索可以很好的解决。农夫约翰搭了一间有N间牛社的小屋。牛舍排在一条直线上，第i号牛舍在xi的位置，但是他的M头小牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是最大化最近的两头牛之间的距离。条件限制：2=N=1000002=M=N0=xi n c; for(int i = 0; i
6、posi; sort(pos, pos+n); int l = 0, r = MAX+1; while(r - l 1) int m = (l+r) 1; if(ok(m) l = m; else r = m; cout l endl; return 0;int n, c;int posmaxn;bool ok(int ma) int cnt = 1; int last = 0; for(int i = 1; i n; i+) if(posi - poslast = c) return true; return false;大家还有什么疑问吗？Thank you！祝大家周日 月赛取得好成绩！奖品丰厚呦
