首页 > 代码库 > 【二分查找学习】
【二分查找学习】
知识准备
结合《算法导论》和《编程珠玑》,下面说明循环不变式的概念与性质。
循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法,它是一个需要保证正确断言。对于循环不变式,必须证明它的三个性质:
初始化:它在循环的第一轮迭代开始之前,应该是正确的。
保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。
终止:循环能够终止,并且可以得到期望的结果。
适用范围
从有序数组中查找某个具体的值
假定一个解并判断是否可行
最大化最小值
最大化平均值
例题
给定长度为n的单调不下降数列A0,A1......An-1和一个数k,求满足Ai>=k条件的最小的i。不存在的情况下输出n。
限制条件
1<=n<=10^6
0<=A0<=A1....<=an-1<10^9
0<=k<=10^9
首先看到这个题目的数据范围,再根据题目的需求——查找,就应该想到二分查找。
如果朴素地使用顺序查找的话,很容易就会超时。
我们假定输入 n=5 a=2,3,3,5,6 k=3
我们先看第n/2的值,如果a[n/2]>=k的话,就可以知道解不大于n/2.
反之如果a[n/2]<k的话,我们就可以知道解大于n/2。
通过这样一次简单的比较,数据的搜索范围缩小了一半。
之后不断重复这样的过程,最终在O(log n)次的比较之内求得最终的解.
代码实现我就搬运白书上面的了=。=
void solve(){ //初始化解的范围 int lb = -1, ub = n; //重复循环,直到解的存在范围不大于1 while(ub - lb > 1){ int mid = (lb+ub)/2; if( a[mid] >= k ){ //如果mid满足条件,则解的存在范围变为了(lb,mid] 左开右闭 ub = mid; }else{ //如果不满足条件,则解的范围变为了(mid,ub] lb = mid; } } printf("%d\n", ub);}
接下来再看看写题时最常遇到的一个问题————最大化最小值(最小化最大值)
例题来源:POJ 2456
题目我手写下:农夫约翰搭了一间有N间牛舍的小屋。牛舍排在一条线上,第i号牛舍在xi的位置。但是他的M头牛对小屋都很不满意,因此经常互相攻击。约翰为了防止牛之间的互相伤害,因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近两头牛直接的距离。 (2<=2<=100000 2<=M<=N 0<=Xi<=10^9)
未完待续
【二分查找学习】