Algorithm for counting number of zeros from sorted array containing 0s and 1s.

Question

I am trying to improve the running time of my algorithm that counts the total number of 0s in an input array. The input array has a length n and consisting of 0s and 1s which are arranged in sorted order.

My algorithm so far is :

Algorithm : zeroCount(A)
Input : An sorted array A containing 0s and 1s
Output : total number of 0s in A

if A[0]=1 then 
    return 0;
len <— A.length
if A[len-1]=0 then
    return len
count <— 0
i <—0
for  i<len do           
    if A[i]==0 then 
        count++
    i++
return count

Java implementation is:

public int zeroCount(int[] a){

    if(a[0]==1)
    return 0;
    int length =a.length;
    if(a[length-1]==0)
        return length;
    int count=0;
    for(int i=0;i<length&&a[i]==0;i++){
            count++;
    }

    return count;
}

However, the running time is O(n). Any suggestions for improving the running time of this algorithm would be appreciated .

Answer 1

Since the input array is already sorted , you can use binary search for better performance. This improves the running time to O(log n).

The algorithm which uses binary search is :

Algorithm : zeroCount(A)
Input : sorted array A containing 0s and 1s
Output : total number of 0s in A

if A[0]=1 then 
    return 0;
len <— A.length
if A[len-1]=0 then
    return len
 return  count(A,0,length)


Algorithm : count(A,lower,upper)
Input :  sorted array A , integers lower and upper 
Output : total number of 0s in A

mid <— (lower+upper) / 2

if A[mid] != A[mid-1] then 
    return mid

if A[mid] != A[mid+1] then
    return mid+1

if A[mid] = 1 then 
    return count(A,lower,mid-1)

if A[mid] = 0 then 
       return count(A,mid+1,upper)

Java implementation :

public int zeroCount(int[] a) {

    if (a[0] == 1)    // all are 1
        return 0;
    int length = a.length;
    if (a[length - 1] == 0)   //all are 0
        return length;

    return count(a, 0, length);
}

public int count(int[] a, int lower, int upper) {
    int mid = (lower + upper) / 2;
    if (a[mid] != a[mid - 1])   
        return mid;

    if (a[mid] != a[mid + 1])    
        return mid + 1;

    if (a[mid] == 1) {                // all are 1 above mid 
        return count(a, lower, mid - 1);  
    } else if (a[mid] == 0) {              // all are 0 below mid 
        return count(a, mid + 1, upper);  
    }
    return 0;
}