Occurrence Count

Given a sorted array input[] of size N with possible duplicate integer elements. Devise an algorithm to find out the count of occurrences of a given number K.
Expected time complexity : O(log N)

Ex [1 3 3 4 4 4 4 4 5 5 6 6 7] K=4
Answer = 5

Solution :

We find first occurrence and last occurrence using binary search.
Then occurrence count would be the difference plus one.

Code :

int bin_search_first_occur(int *a,int low,int high,int data)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if((a[mid]==data && mid==low) || (a[mid]==data && a[mid-1]<data))
            return mid;
        else if(a[mid]>=data)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}
int bin_search_last_occur(int *a,int low,int high,int data)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if((a[mid]==data && mid==high) || (a[mid]==data && a[mid+1]>data))
            return mid;
        else if(a[mid]<=data)
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}

int occurrence_count(int []input, int N, int K){

return bin_search_last_occur(input, 0, N-1, K) - bin_search_first_occur(input, 0, N-1, K) + 1;

}

Complexity :

• Time : O(log N)
• Space : O(1)