Finding a White-Black Pair

White-black pair

Consider an array of white and black cells, where the first cell is white and the last cell is black. A white cell followed by a black cell in this array is called a white-black pair. Here is an example of an array with six white-black pairs.

However, we don’t see the colors of the cells (except for the first and the last ones). For us, the array looks like this:

Finding a white-black pair using binary search

We might point to any cell and ask the question, What is its color? Our goal is to find a white-black pair by asking the minimum number of questions. Try the interactive puzzle below. After solving this puzzle, we’ll see that the binary search is useful even when the data is not sorted!

But how do we know that there’s a white-black pair? This is true because when moving from the first white cell to the last black cell, the color of a cell should eventually switch from white to black at least once.

Even though this proof works for any array that starts from a white cell and ends in a black cell, it is non-constructive: it proves that there exists a white-black pair, but doesn’t give an efficient method for finding this pair (by revealing the color of a few cells). In particular, if we start checking the color of the cells one by ...