资源描述：
《二分查找及其应用复习课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、二分查找及其应用—ByElemenT今天，你AC了吗？NO!YES!请在这里输入您的标题刷题太无聊？我们玩游戏吧！相信大家都玩过猜数字的游戏。两人游戏，A同学在心里默念一个整数n（1<=n<=1000）。B同学猜n是多少。同时如果B没有猜对，A告诉他这个数比默念的数高了还是低了。最坏情况下，ElemenT也不用超过十次可以猜出！最坏情况下需要多少次呢？看起来好厉害的样子其实并不是，下面将引入“二分搜索”的概念。如上述的游戏中，第一次应该取多少呢？500！很不巧并不是500，而是一个比500大的数。虽然运气不好，但是B将区间的范围砍掉了一半！那么下一次
2、B该猜什么。。。大家已经发现，问题变成了501-1000之间猜一个数，那么应该猜 (501+1000)/2=750! 如果运气还是不好，，又猜小了. 没关系！只猜了仅仅两次，我们就将区间缩小为751--1000. 那么继续下去...我们发现，每次可以将区间缩小为原来的一半。递减速度显然就是log级别的。 log(1000)向上取整只有10. 那么我们一定可以在10次之内猜出这个数。给定一个有序序列a0,a1,a2...aN，给出一个目标值tg，在序列中查找是否存在tg，如果存在，返回tg的下标。 如何快速查找？我们必须看到数列是有序的充分利用有序
3、的条件，类似猜数一样查找tg。复杂度为log(n)。那么我们来看看如何实现二分查找。intbs(int*a,intn,inttg){ intl=0,r=n-1; while(l<=r){ intmid=(l+r)/2; if(a[mid]==tg)returnmid; elseif(a[mid]>tg)r=mid-1; elsel=mid+1; } return-1; }二分查找的应用（二分答案）假定一个解判断是否可行最大化最小值最大化平均值有N条绳子，它们长度分别为Li。如果从他们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？答案保留
4、两位小数。1<=N<=10^4,1<=K<=10^4,1<=Li<=10^5样例输入N=4,K=11,L={8.02,7.43,4.57,5.39}样例输出2.00(每条绳子可以得到4,3,2,2共计11条)另C(x):=可以得到K条长度为x的绳子问题转化为求满足C(x)条件的最大的x。C(x)=(Li/x的总和是否大于K)因此，计算C(x)的复杂度是O(n)那么只要二分枚举x，就可以解决此题！intmain() { cin>>n>>k; for(inti=0;i>a[i]; doublel=0,r=100001; for(i
5、nti=0;i<100;i++){ doublem=(l+r)/2; if(ok(m))l=m; elser=m; } printf("%.2f",0.01*(int)(l*100)); return0; }intn,k; doublea[maxn],tot=0; boolok(doublex){ intnum=0; for(inti=0;i=k)returntrue; returnfalse; }再看一道最大化最小值的例题 这类问题通过二分搜索可以很好的解决。农夫约翰
6、搭了一间有N间牛社的小屋。牛舍排在一条直线上，第i号牛舍在xi的位置，但是他的M头小牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是最大化最近的两头牛之间的距离。条件限制： 2<=N<=100000 2<=M<=N 0<=xi<=10^9 样例输入 N=5,M=3,x={1,2,8,4,9} 样例输出 3 (在位置1,4,9放3头牛)另C(d):=可以安排的牛的位置使得最近的两头牛的距离不小于d 问题就变成了求满足C(d)的最大的d。 每次判断对每头牛最多处理一次，因此判断
7、的复杂度是O（n） 总复杂度O(n*log(INF))intmain() { cin>>n>>c; for(inti=0;i>pos[i]; sort(pos,pos+n); intl=0,r=MAX+1; while(r-l>1){ intm=(l+r)>>1; if(ok(m))l=m; elser=m; } cout<8、os[i]-pos[last]=
