Tuesday 19 August 2014

Count Number of zeros in sorted Array

Given a sorted array of 0’s and 1’s. Find out the no. of 0’s in it. Since Array is sorted already, it is better to use Binary search.

public class BinarySearch {
    static int binarySearch(int a[], int low, int high){
        if(low > high)
            return -1;
        int mid = (low+high)/2;
        if((mid !=a.length-1) && a[mid] != a[mid+1]){
            return mid+1;
        }
        else if (a[mid] == 0){
            low = mid+1;
            return binarySearch(a, low, high);
        }
        else{
            high = mid-1;
            return binarySearch(a, low, high);
        }
    }
    
    public static void main(String args[]){
        int a[] = {0,0,0,1,1,1,1};
        System.out.println(binarySearch(a, 0, a.length-1));
    }
}

Output
3


Prevoius                                                 Next                                                 Home

No comments:

Post a Comment