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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Shaull Feb 20 '13 at 16:12
  • 1
    $\begingroup$ Hi Shaull, please take a looj at the original question postimage.org/image/tfeqe7t93 $\endgroup$ – Avish Feb 20 '13 at 17:16

After viewing the original question, it seems that you have an additional piece of information: you know that the first element is 1 and that the last element is 0. This is crucial!

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.