Simple C++ Solution in O(log(n))


#1
int firstOccurance(const vector<int>& A, int B)
{
    int left=0, right=A.size()-1,mid;
    while(left<=right)
    {
        mid = (left+right)/2;
        if(A[mid]==B && (mid==0 || mid>0 && A[mid-1]!=A[mid]))
            return mid;
        else if(A[mid]<B)
            left=mid+1;
        else
            right=mid-1;
    }
    return -1;
}

int lastOccurance(const vector<int>& A, int B)
{
    int left=0, right=A.size()-1,mid,n=A.size();
    while(left<=right)
    {
        mid = (left+right)/2;
        if(A[mid]==B && (mid==n-1 || mid<n-1 && A[mid+1]!=A[mid]))
            return mid;
        else if(A[mid]>B)
            right=mid-1;
        else
            left=mid+1;
    }
    return -1;
}

int Solution::findCount(const vector<int> &A, int B)
{
    int first = firstOccurance(A,B);
    int last = lastOccurance(A,B);
    if(first!=-1&&last!=-1)
        return last-first+1;
    else
        return 0;
}