1

Assume we have a binary array A of size n and all 1 are in the middle and all 0 are on both sides like 00011000. We don't know the number of 1's and the array could be not symmetric, and we are guaranteed that at least 1 position i that A[i]=1 and at least one position j:j<i, A[j]=0 and at least one position k:k>i, A[k]=0.

What could be the efficient algorithm, perhaps with complexity like poly(log n), to find the separation index between 0 and 1, i.e., the index i such that (A[i]=1,A[i-1]=0) or (A[i]=1, A[i+1]=0)? Do we have a name for this problem ?

Improve this question
1
  • 2
    The question is unclear. What are the constraints? Is the array symmetric? Is there at least one 0 and one 1? What do you mean by separation index? Commented Nov 26, 2020 at 21:48

1 Answer 1

Reset to default
2

The trivial solution is optimal

You will likely have noticed that you can solve this problem in linear time simply by iterating over the array.

Now, consider the situation in which there is only a single 1 in the array. All we can do to find this 1 is to check every position until we find it. So long as the 1 has not been found, we will only find 0's which give us no information as to the whereabouts of the 1. Of course, we don't need to check the first or last element of the array as they are guaranteed to be 0, but this does not help significantly.

You can do better on a quantum computer

On a quantum computer you can use Grover's algorithm to find a 1 in O(sqrt n), after which you can find either of the separation indices with a simple binary search, for a total of O(sqrt(n) + log(n)) = O(sqrt n).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.