有若干盒子排成一列，已知第1个盒子不是空的，从第1个到第个都不是空的，但是从此往后的盒子都是空的。但是，打开每个盒子看是需要一定时间的，比如需要时长。已知，请问如何能够在最短的时间内找到这个盒子？

思路一：逐项法

也就是逐项去看盒子是不是空的。这种情形下，需要看次。

思路二：二分法

举个简单的例子，取。

，四舍五入至6，看第6个盒子是不是空的。结果一看，是空的，则介于1~6之间。

，四舍五入至4，看第4个盒子是不是空的。结果一看，不是空的，则介于4~6之间。

，看第5个盒子是不是空的。结果一看，不是空的。

现在已知第5个盒子不是空的，第6个盒子是空的，则。

通过这个例子可以大概感觉到，看多少次，是看从n除以多少次2以后，能达到或小于1。即求解，解得，也就是大概需要次。我们知道，当时，总有。因此，二分法比逐项法要好。

思路三

难道就没有别的方法了吗？试试嘛。比如，先看第100、200、300、……个盒子是不是空的。照这个顺序去看，发现的第一个空盒子，记为，比如是600，则说明最后一个非空的盒子是在第500个和第600个之间。然后再用二分法，在500~600的范围内找。

那么问题来了，你为什么要设定公差是100，而不是200，即先看第200、400、600、……个盒子？

先找一个最优的公差吧，然后再看看这是不是比二分法要快。

记这种方法需要看次盒子。则有

记右式为，则。

	0	+	0	-
		单调增加		单调减少

因此当时，取得最小值。

与二分法的相减得：

令，则解得
其中。

也就是说，当最后一个盒子的序号大致小于的四分之一时，思路三更快，否则是二分法更快。

总结

这思路三的方法有什么用？

反正我是用它找Excel中某一张表的最后一行，反正比自带的Sheet.UseRange.Rows.Count要快。