Algorithm for counting the number of zeros from a sorted array containing 0 and 1 sec.

Question

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

My algorithm so far:

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:

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 operating time is O (n). Any suggestions for improving the running time of this algorithm will be appreciated.

Answer 1

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

An algorithm that uses binary search:

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;
}

Answer 2

, (, i) 0 . 0s (i + 1).

  int CountOfZeroes(int[] A, int key)
        {
            int low = 0;
            int high = A.size - 1;              
            int result = -1;

            while (low <= high)
            {
                int mid = low + (high-low)/2;

                if (A[mid] == key)
                {
                    result = mid;
                    low = mid + 1;
                }
                else if (key < A[mid])
                {
                    high = mid - 1;
                }
                else 
                {
                    low = mid + 1;
                }
            }

            return result + 1;              
        }

, 0. O(log n).