漫话二分（下）
很多问题并不完全符合二分的模型。最常见的一个情况估计应该是无穷长的有序队列中的二分查找问题。例如，前文所提到的求解x^x=a实际上就是这样的问题，这里x的取值范围可以是大于0的所有实数。当然，这里的x明显有一个上界，比如x明显要比a小。但是，如果有什么二分问题，它没有一个明确的上界呢？比如，我们再玩一次猜数游戏，我想一个数，然后告诉你你的猜测是大了还是小了。不同的是，我不告诉你这个数是在什么范围内选的，我想的数可以是任意一个正整数。那你该怎么办呢？最初的想法当然是，不断往大的猜，直到某个时候它超过了目标值为止；然后以它为上界，剩下的就可以看作有限多了。关键是，我们以什么样的跨度来枚举这个上界？首先必须肯定的是，这个上界枚举序列必须是发散的，否则会有数我们一辈子也猜不到；同时，线性增长的策略也是很傻的：跨度太小了你可能得到猴年才能找出上界，跨度太大了的话一来就确定了上界，但待考虑的队列也可能远远超过所需。一个比较灵活的想法是：按照1, 2, 4, 8, 16, …, 2^n的序列来猜测上界。这是一种“相对大小”的思想：既然连前面N个数都小了，我们也就不在乎那么一两个了，不妨直接再跳过N个数直接考察2N。这样的话，整个猜测过程仍然保持log(n)的复杂度，整个算法也更加美观一些。 假如你有一台时光机，可以让你到任意远的未来去，你打算怎么来使用它？或许你会说，先去100年后看看，生活一年之后再去200年后体验体验，然后再去300年后生活一年，再去400年后生活一年……其实，这种线性的时光旅行并不科学。当你已经跨越了数千年以后，相比之下100年的跨度已经不算遥远了，1000年后与1100年后的差异远远没有今天和100年以后的变化那样令人震撼。我说我和Stetson MM的思维如出一辙，那不是说着好玩的。一次MSN聊天时我们讨论到这个话题，两人同时想到了这样的时间旅行方式：先直接跳到1年后生活，再到2年后生活一段时间，再到4年后，再到8年后……用这种方式来体验未来，即使我在每一个时间点停留一年，我也能保证见到从我余生的感情生活到人类文明的各种不可思议的形态，甚至到文明的轮回与宇宙的毁灭等各种尺度下的牛B事。我的确能够看到充分远的未来，了解到足够宏大的文明史和宇宙史：假设我还能活80年，那么我可以看到2^80=1208925819614629174706176年内的种种，这么多年里估计就是宇宙热寂也该结束了。 折纸后的高度、在棋盘里放米、Hanoi塔与世界末日……无数火星的例子告诉我们，倍增的力量是异常强大的。如果你不信的话，下次来北京时请我喝酒，不妨这样来试试：先我喝一杯，你喝一口；然后我喝一杯，你喝两口；然后我喝一杯，你喝四口……看咱俩谁坚持的久。