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
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?