I have been stuck in that question from Coursera AlgorithmicBox. The question of Quiz is as below. I do not have any idea how to approac for the solution :)

You are given 20 black and white cells. The leftmost one is white, the rightmost one is black, the colors of all other cells are hidden. You can reveal the color of a cell by clicking on it. Your goal is to find two adjacent cells of different colors by using at most 5 clicks.

CodePudding user response：

Since there is white cell and a black cell, we know that there is a transition at some point. We can click on the 10th cell, if it's white we discard the cells left of it, if it's black, the cells right of it, we'll be left with 11 (or 10) cells, if we repeat this process using the middle, or one of the two middle cells in the case of even tiles one more times, we'll have at most 6 cells. We repeat this process again to discard two more cells and we're left with 3 cells, we then check the last cell to see all 3 cells. Since we know that the left and right cells are different, it's either the first two or last two that are different but adjacent.

We used 4 clicks.

In general this is similar binary search, with similar guarantees. we always check for the floor[n/2] th cell (or ceil, doesn't matter).