在 万仓一黍 的博客中看到了“一道有趣的面试题 ”这篇文章，文中给出了一种解法，仔细想了一下，发现也可以在常数时间复杂度下解决。
题目：
某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。
例如：有这样一种方式，第一次选择在60层扔，若碎了，说明临界点在60层及以下楼层，这时只有一颗珠子，剩下的只能是从第一层，一层一层往上实验，最坏的情况，要实验59次，加上之前的第一次，一共60次。若没碎，则只要从61层往上试即可，最多只要试40次，加上之前一共需41次。两种情况取最多的那种。故这种方式最坏的情况要试60次。
解：
原题是，已知大楼的高度，求最少的实验次数。现在为了便于计算，先把题目反过来考虑：
还是上面的实验，已知进行实验K次可以得到了临界楼层，求这个楼的最大高度H。
开始实验：
第1步：任取一个楼层H1 （1 =< H1 <= H），用第一颗珠进行实验，如果珠碎，则用低二颗珠从第一层向上逐层进行实验，在最坏情况下， 实验次数为K1=H1 ，即可得到结果。否则，如果第一个珠碎了，并且 H1!= H 则令 i=2 进行第二步实验。
第2步：任取一个楼层Hi (Hi-1<Hi<=H,),用第一颗珠进行实验，如果珠碎，则用低二颗珠从第一层向上逐层进行实验，在最坏情况下， 实验次数为Ki = i - 1 + Hi - Hi-1 ，即可得到结果。否则，如果第一个珠碎了，并且 Hi != H ， 则令i=i+1，回第2步接着实验。
因为楼层高度H是有限的，实验会在有限步内停止，在最坏的情况下，Hi=H 时实验结束，将此时的 i 记为n。即：
Ki = H1 (i=1) （等式 1.1）
Ki = (i – 1) + Hi - Hi-1 （1<i< n） （等式 1.2）
Ki = (n – 1) + H - Hn-1 (i=n) （等式 1.3）
将上面的等式按 i=1,2,3…n 相加可得：
K1 + K2 + K3 + … + Kn=1 + 2 + 3 + … + (n-1) + H =n*(n-1)/2 + H
即：
H = (K1 + K2 + K3 + … + Kn) - n*(n-1)/2
因为 K = max(K1, K2, K3, … , Kn) 是已知的, 所以当K1 = K2 = K3 = … = Kn = K 是 H 取得最大值
所以：
H = n *k - n*(n-1)/2 (等式 1.4)
等式1.3 可以写成 K = (n – 1) + Hn - Hn-1 可得
Hn - Hn-1 = K + 1 – n > 0
即 n<K+1 ,
所以 n的取直范围是 1=< n <=K
等式1.4 是关于n的二次函数， 当n = k 时 等式1.4取得最大值，最大值是 ：
H = K（K+1）/2 （等式 1.5）
这就求出了 K 次实验能确定临界层的最大楼层高度。
下面在把题目正过来，考虑原题：
由等式1.5 ， k-1次实验能确定临界层的最大楼层高度为H’=k (k-1) /2
则，如果楼层的高度 x 在区间（H’ , H] 范围内，则最多进行K次实验即可的到临界层 。
即
K(K-1)/2 < x <= k(K+1)/2 (不等式 1.6)
将不等式 1.6 各项 × 2 得：
k(K-1) < 2*x <= k(K+1) (不等式 1.7)
而
(K-1)^2 < k(K-1) < K^2 < k(K+1) <(K+1)^2
即，不等式 1.7 所确定的个区间中有且仅有1个完全平方数，则找出与2*x 近似的完全平方数K^2 , 那么K就是最终的结果。
计算的时候分别算出
K1 = floor( sqrt (2*x))
K2 = ceil(sqrt (2*x))
分别将 K1, K2 带入不等式 1.6 ，可得到两个区间，如果x在第一个区间中则结果是K1， 否则是K2 .
/*c语言源码*************************************/
#include<stdio.h>
#include<math.h>
int fun (int x)
{
int k = (int)sqrt(2.0*x);
int up = k*(k+1)/2;
return x <= up ? k :k+1 ;
}
int main()
{
int i;
for (i=1; i<=100; ++i) /*用1到100之间的数测试*/
printf("%d\t",fun(i));
return 0;
}