Give a Monte Carlo algorithm for the previous problem that examines at most [log n] entries in A and succeeds in finding a 1 in A with high probability.

Data From Previous Problem

Suppose A is an array of n bits, half of which are 0’s and half of which are 1’s. But the bits in A can be in any order, so that the worst-case performance of any deterministic algorithm for finding a 1 in A is Θ(n). Give a Las Vegas algorithm that finds a 1 in A in O(log n) time with high probability.