# Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking about everything that might happen in case of robbery, one problem came into my mind and it can be described as follows.

Suppose that you and your family decided to go on a trip abroad, that would last for around 7 days. After spending some nice time with your family, you return back only to realize that your home had been robbed. You call the police and the police asks for the data stored in the camera.

Now, you know for sure that the robbery happened during those 7 days that you were gone, and you definitely know that the camera will show the people doing the robbery at some specific point of time, problem is, you do not know when.

Now, assuming that no one had seen anything at all and that the only source of information would be the data stored by the camera, how would the police find the time during which the robbery happened? Can they do something better than watching every single second of the footage available?

In computer science terms, assume that you are given an array of size $N$, where all the elements are white, except for one which is black. Now you can imagine that the white elements are just images stored by the camera and the indexes of the array represent seconds. If no robbers are depicted in the image, then this image is white, otherwise it is black.

So now you want to find that second where the robbers are depicted in the image, so you are looking for the index of the black element in your array. Can you do better than actually scanning the entire array to find that index?

• In the non-theoretical version of the question, it's likely that the portion of the video recorded after the break-in would have some indication that the break-in happened in the past -- a broken window, muddy footprints, missing television, etc. In that case, binary search would be the most efficient way to zero in on the time of the crime; look at a frame 3.5 days in to start, cutting the timespan in half each time you establish a frame as either before or after the break-in. Doesn't work for the one-black-frame case, of course. – Russell Borogove Jun 26 '15 at 22:26

For your problem with the array: No, there is no better algorithm. That's the best you can do. Any deterministic algorithm will in the worst case have to look at every array element (technically: at least $n-1$ of the $n$ elements).
This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at $n-2$ elements and hasn't found the black element yet. Then I claim a correct algorithm has to examine at least one more array element. If it doesn't, then look at what output it produces, and see which of those two elements it blames; you can now construct an array that puts the black element at the other element (the one it didn't blame and hasn't looked at yet). That array will be entirely consistent with everything the algorithm has seen so far, so the algorithm will produce the wrong output on that array.