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

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

well cos like a ds it doesn't really die out, unlike for example, fifa, they always come out with a new version, so lets say your fifa 18 is charging you to update the teams and stuff, so, if messi were to go to real madrid (never gonna happen) it would switch messi to the other team, until the owners of fifa come out with fifa 19, then the game would eventually stop updating, and back to the ds, it doesn't really stop working after sometime because there's lots of things that it could be used for, and idk if u know what i'm saying, but long story short, samsung, represents the ds, if they still work, and people love them but not the new version, the old version still works, so they don't really force people to buy new phones, get me?