Question

You are given an array A(1...N), where N is a power of 2. For some n ≤ N, the first n cells are filled with the bit 0. The rest of the cells are filled with the bit 1. You are not given the value of n. Describe an algorithm that finds the number of 0’s in the array, and runs in time O(log n). Explain in English what your algorithm does and why your algorithm runs in time O(log n).

Answer 1

See explaination

Step-by-step explanation:

Binary(A,low , high )

if low> high

return -1

mid= (high+low)/2

if(A[mid]=1) and ((mid=0) or (A[mid-1]==0)) then

return mid

else if A[mid==1] then

return Binary(A,low,mid-1)

else

return Binary(A,mid+1,high)

Having in mind that the given array is a sorted array, we can simply use the binary search here, to find either lower bound of 1 or upper bound of 0.

I am explaining here by finding the lower bound 1.

You can see in the algorithm that, each time our size is getting reduced by half, so overall complexity of this algorithm is O(logn).