首页 > 代码库 > 【二分查找学习】

【二分查找学习】

知识准备

结合《算法导论》和《编程珠玑》,下面说明循环不变式的概念与性质。

循环不变式主要用来帮助理解算法的正确性。形式上很类似与数学归纳法,它是一个需要保证正确断言。对于循环不变式,必须证明它的三个性质:

初始化:它在循环的第一轮迭代开始之前,应该是正确的。

保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。

终止:循环能够终止,并且可以得到期望的结果。

适用范围

从有序数组中查找某个具体的值

假定一个解并判断是否可行

最大化最小值

最大化平均值

例题

给定长度为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)

 

未完待续

 

【二分查找学习】