Ask 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).

+4
Answers (1)
  1. 6 December, 16:18
    0
    See explaination

    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).
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers