Given a sorted array with duplicate elements, find the number of occurrences of x.

Solution #1: We will use the modified binary search to solve this in O(log n) time. Here is the code,

int count(int* arr, int x, int start, int end)
{
    if(start > end)
        return;

    int mid = (start+end)/2;
    int cnt = 0;

    if(arr[mid] == x)
        cnt = 1 + count(arr, x, start, mid-1) + count(arr, x, mid+1, end);
    else if(arr[mid] > x)
        cnt = count(arr, x, start, mid-1);
    else
        cnt = count(arr, x, mid+1, end);

    return cnt;
}