循环不变式与二分查找

去年研读了《算法导论》，对我而言书中一个“循环不变式”的概念很新颖。当时并未体会到这个概念的用处，似乎只是用来证明算法正确性而已。直到昨天做USACO上Fence Rails那道题的时候，我突然发现循环不变是在算法实现或者说程序书写时也很有帮助。

首先，我觉得maigo的程序里那个二分答案写得不好——有可能某个ok(m+1)要被检查两次，而这很有可能成为TLE的原因！真的要在每次检查ok(m)后紧接着检查ok(m+1)吗？也许可以避免吧。

这时我想到了循环不变式。我们需要的是找到一个明晰的界限x，满足ok(x)为true而ok(x+1)为false。 那么我们设计如下循环不变式：ok(l)为true，ok(r)为false。而每一次迭代都严格的缩小r-l，当r-l==1时便结束。当然为了满足初始条件，初始时l=0，r=R+1。有了这个循环不变式，在写代码时的思考也就减轻了：m=(l+r)/2；如果ok(m)为false，那么l=m；反之r=m。循环不变式就这样得到保持。最后的程序非常简洁高效（至少在二分答案这一环上是比maigo的程序简洁高效的）。

把这种思想用到其它类型的二分查找里，比如说需要实现C++里的upper_bound类似的东西。欲查找对象为x，查找的数组是s。那么循环不变式就是：s[l]<=x，s[r]>s。每次循环中，s[m]<=x则l=m，反之则r=m。同样是r-l==1时终止返回l。

我们看出， 在程序实现过程中试图设计循环不变式有以下好处：1. 使编程思路明晰，不易出低级错误。这是最重要的。 2. 保证程序正确性。 3. 使程序简洁，而且往往比较高效。4. 降低写代码时的思考强度，加快书写速度。

什么时候应该往循环不变式的方面想呢？我目前只想到了一条：当你写出了一个for( ; ; )的时候。这个有待进一步研究和补充。