在排序列表中搜索饱和度值的最佳方法

Math Battle的一个问题.在我的一次求职面试中,我也问过这个特殊的问题.

"一只猴子有两个椰子.从M层建筑的阳台上扔下椰子就搞错了.当椰子被打破时,猴子想知道最低的楼层.确定这个事实所需的最小尝试次数是多少？ "

条件:如果椰子被破坏,你就不能重复使用.你只剩下另一个椰子

我能想到的可能的方法/策略是

二进制分手,一旦你发现椰子破碎的地板使用了从最后发现的二元分手下调指数.

窗口/切片较小的地板组和使用二进制分解窗口/切片(但在下方这将需要它自己的切片算法.)

想知道是否有其他方法可以做到这一点.

1> Brian R. Bon..：

---

这样的面试问题旨在让您了解自己的想法.所以我可能会提到如上所述的O(N ^ 0.5)解决方案,但我也会给出以下讨论......

由于椰子可能随时间内部开裂,因此结果可能与O(N ^ 0.5)溶液不一致.虽然O(N ^ 0.5)解决方案是有效的,但它并不完全可靠.

我会推荐使用第一个椰子的线性O(N)溶液,然后用第二个椰子验证结果.其中N是建筑物中的楼层数.所以对于第一个椰子你尝试1楼,然后是第2个,然后是第3个,...

假设两个椰子在结构上完全相同并且以完全相同的角度落下,那么你可以将第二个椰子直接扔在第一个椰子破坏的地板上.叫这个破椰子楼B.

对于椰子#2,你不需要在1..B-1上进行测试,因为你已经知道第一个cocounut没有在B-1,B-2楼层上打破...... 1.所以你只需要在B上试一试

如果第二个椰子在B上破裂,那么你知道B是有问题的地板.如果它没有破裂你可以推断出椰子会随着时间的推移而发生内部开裂和降解,并且测试开始时是有缺陷的.你需要更多的椰子.

鉴于建筑规模非常有限,您对解决方案的额外信心值得O(N)解决方案.

正如@RafałTowgird所说,解决方案还取决于所讨论的猴子是非洲猴还是欧洲猴.众所周知,非洲猴子的力量更大.因此,使破碎地板B仅准确地具有+/- 2层的变化.

为了保证猴子不会从所有这些楼梯上感到疲倦,建议在第一个椰子上附上一根绳子.这样你就不需要为第一个椰子做1 + 2 + .. + B = B*(B + 1)/ 2级楼梯.你只需要做B级楼梯.

可能看起来楼梯的数量与这个问题无关,但如果猴子一开始就累了,我们可能永远不会找到解决方案.这为停止问题提供了新的考虑因素.

我们还假设建筑物位于地球上,重力设定为9.8m/s ^ 2.我们还假设不存在引力波.

---

谢谢你的解释..喜欢细节..椰子不均匀,非洲vs欧洲猴子,悬挂字符串和停止问题..很棒的答案.. !!

---

+1讨论椰子不均匀性.我也不会错过破解一些Monthy Python笑话的机会("非洲或欧洲猴子？").

2> recursive..：

---

二分搜索不是答案,因为您只有一次机会高估.二进制搜索需要log m最大限度的估计.

这是一个两阶段的方法.首先是以相对较大的步骤迭代地板.第一个椰子破碎后,第二个阶段是在最后一个安全地板后开始尝试每个楼层.

大的步骤大致是sqrt(m),但它们早期更大,后期更小,因为如果第一个椰子早期破裂,你可以在第二阶段提供更多的迭代.

StepSize = (minimum s such that s * (s + 1) / 2 >= m)
CurrentFloor = 0

While no coconuts broken {
    CurrentFloor += StepSize
    StepSize -= 1

    Drop coconut from CurrentFloor
}

CurrentFloor -= StepSize + 1

While one remains coconut unbroken {
    CurrentFloor += 1
    Drop remaining coconut from CurrentFloor
}

// CurrentFloor is now set to the lowest floor that will break the coconut, 
// using no more total drops than the original value of StepSize