二分查找的变形：猜数字问题与扔鸡蛋问题

1.猜数字问题：

      A、B两个人在玩猜数字游戏，A随机写了一个数字，在[1，100]区间之内，将这个数字写在了一张纸上，然后B来猜。

     如果B猜的数字偏小的话，A会提示：“数字偏小”

     一旦B猜的数字偏大的话，A以后就再也不会提示了，只会回答“猜对 或 猜错”

     问： 乙至少猜(13)多少次才可以准确猜出这个数字，在这种策略下，乙猜的第一个数字是(13)

[解析]：

      首先阅读题目，一个很重要的信息点就是： 一旦B某次猜的偏大，A就不再提示，此次之后B猜的偏小A也不会再提示，只回答猜对与否 。如果没有这个条件，或者说改变这个条件，改为： 如果B猜的偏大，A会提示B这次猜的偏大 那么相信大家都会给出答案，那就是用二分法，只需要7次就可以保证猜对了。

      但是现在的条件变了，如果B猜的偏大，那么不提示，所以我们得出结论就是：如果猜的偏大，只能一个一个往下猜。

      答案是13次，猜测序列为14, 27, 39, 50, 60,69, 77, 84, 90, 95, 99，哪一次偏大了，就在该数与上一个数的区间一个个猜，最多13次一定能猜到。下面讲讲解题思路：

      刚一看到这道题，熟悉二分查找的同学肯定马上想到要用二分查找来猜，第一个猜50，第二个猜25或者75……可是这样有一个问题，传统的二分查找是需要每次都知道是偏大还是偏小的，但这里一旦偏大，就再也得不到这个信息了。这就导致了在这里如果继续使用这种类似二分查找的方法，最坏情况下的猜测次数分布不均匀。

      直觉告诉我们，要使得总猜测次数最少，那就让最坏情况下的猜测次数分布均匀即可。假设最多猜测k次，那么第一个猜的数字应该是k+1，因为若偏大了，则逐一把k, k-1, ……2的共k-1个数猜一遍，最坏的情况是都没猜中，则1必定是正确结果；若偏小了，则继续按照下面的方式猜：

      若偏小了，则第二个猜的数字x应该是什么呢？这就要使得若第二次猜偏大了的话，必定能把总共的猜测次数也控制在k次，因此第二个猜的数x跟第一个猜的数k+1之间应当间隔k-1个数，因为这样的话，即使第二个数偏大了，则逐一把x-1,x-2,……k+3的共k-2个数猜一遍，必定能得到答案。因此第二个猜的数字x为2k+1。

      依此类推，要把100覆盖，则可列出不等式：(k+1) + k + (K-1) + …… + 2 >= 100，解得k >= 13

2.与之类似的扔鸡蛋问题：

      假设你有2个鸡蛋，你现在想知道这些鸡蛋的硬度。你家住在100层高的大楼里，现在要在这座大楼上测试鸡蛋的硬度。每个鸡蛋的硬度相同，鸡蛋的硬度定义为：如果鸡蛋从第m层上掉下来没有破裂，而从第m+1层上掉下来就破裂了，那么这个鸡蛋的硬度就是m。某个鸡蛋如果在实验中破裂了就永远的损失了。要求提供一种方案，在最坏情况下做最少次数的实验即可把鸡蛋的硬度检验出来

    扔鸡蛋问题的原型(原题见《算法》P133习题1.4.24~1.4.25)：假设你面前有一栋N层的大楼和许多鸡蛋，假设将鸡蛋从F层或者更高的地方扔下鸡蛋才会摔碎，否则则不会。设计一种策略来确定F的值，其中扔~lgN次鸡蛋后摔碎的鸡蛋数量为~lgN。

    可采用二分查找。

     怎样将成本降低到~2lgF ？

     可以先按照1,2,4,8……的序列找出F的值在哪个区间，然后对该区间进行二分查找。

      现在限定只有两个鸡蛋，而你的成本模型则是扔鸡蛋的次数(这和查找命中(鸡蛋完好无损)比未命中(鸡蛋摔碎)的成本小得多的情形类似)。设计一种策略，最多扔2√N次鸡蛋即可找出F。

      采用桶查找策略。将楼层区间均分为√N个大小为√N的子区间，先用第1个鸡蛋对各区间的边界构成的序列进行顺序查找，找出F在哪个区间。再用第2个鸡蛋对该区间进行顺序查找。

   　怎样将成本降低到~2√F 次？

      可以先用第1个鸡蛋按照1,4,9,25……的序列找出F的值在哪个区间，再用第2个鸡蛋对该区间进行顺序查找。