谜题：两个相邻的相反颜色的单元格

Question

我一直卡在 Coursera AlgorithmicBox 的那个问题上。测验的问题如下。我不知道如何解决这个问题:)

给你 20 个黑白单元格。最左边的是白色的， 最右边的一个是黑色的，所有其他单元格的颜色都被隐藏了。你 可以通过单击显示单元格的颜色。你的目标是找到 两个不同颜色的相邻单元格，最多点击 5 次。

Answer 1

因为有白色单元格和黑色单元格，我们知道在某个时刻有一个过渡。我们可以点击第 10 个单元格，如果它是白色的，我们丢弃它左边的单元格，如果它是黑色的，我们丢弃它右边的单元格，如果我们使用中间的重复这个过程，我们将剩下 11（或 10）个单元格，或者在偶数块的情况下两个中间单元格之一，我们最多有 6 个单元格。我们再次重复此过程以丢弃另外两个单元格，剩下 3 个单元格，然后我们检查最后一个单元格以查看所有 3 个单元格。因为我们知道左右cell是不同的，所以要么是前两个，要么是后两个是相邻的。

我们使用了 4 次点击。

一般来说，这是类似的二分查找，具有类似的保证。我们总是检查 floor[n/2] 单元格（或 ceil，无关紧要）。