Easy cpp solution with comments


#1

int binarySearch(const vector &arr, int l, int r, int x)
{
if (r < l)
return -1;

int mid = l + (r - l) / 2; 

// If the element is present at the middle 
// itself 
if (arr[mid] == x) 
    return mid; 

// If element is smaller than mid, then 
// it can only be present in left subarray 
if (arr[mid] > x) 
    return binarySearch(arr, l, mid - 1, x); 

// Else the element can only be present 
// in right subarray 
return binarySearch(arr, mid + 1, r, x); 

}
int Solution::findCount(const vector &A, int x) {
int n = A.size();
int ind = binarySearch(A, 0, n - 1, x);

// If element is not present 
if (ind == -1) 
    return 0; 

// Count elements on left side. 
int count = 1; 
int left = ind - 1; 
while (left >= 0 && A[left] == x) 
    count++, left--; 

// Count elements on right side. 
int right = ind + 1; 
while (right < n && A[right] == x) 
    count++, right++; 

return count; 

}