# Finding a '1' cell with a '0' to its right in a binary array

Given an array of size n that holds ones and zeros I need to find an index of a 1 cell that has 0 to his right (in then next cell) there could be more than one pair in a given array, any one of them is fine. The array is not sorted, but we do know that the first element is 1 and the last element is 0.

The search should be in $O(\log n)$ time. I'm thinking that a binary search variation is the answer but I'm not sure how.

• Are you sure that these are all the assumptions you have? Are you allowed to pre-process the array? If not, this sounds impossible: any deterministic algorithm that operates in time $f(n)<n$ can examine at most $f(n)$ cells. Suppose these cells are all $1$'s, then what does the algorithm do? Given an algorithm, it is easy to construct an array for which this will happen, and we will still have plenty of room to place the pair $1,0$, so the algorithm cannot answer correctly. Feb 20 '13 at 16:12
• Hi Shaull, please take a looj at the original question postimage.org/image/tfeqe7t93 Feb 20 '13 at 17:16

So indeed you can solve it with binary search: first observe that if the first element is 1 and the last is 0, there must be subsequence of the form $1,0$ in the array.
Denote the array by $A[1,...,n]$. If $A[n/2]=1$, then there is a $1,0$-subsequence in the subarray $A[n/2,...,n]$. If $A[n/2]=0$, then there is a $1,0$-subsequence in the subarray $A[1,...,n/2]$.
So you can use Binary search, which takes $O(\log n)$ time.