Given a sorted array and a number x, write a function that counts the occurrences of x in the sorted array

Given a sorted array and a number x, write a function that counts the occurrences of x in the array. Expected time complexity: O(Logn)
For example:

Input arr = {2, 2, 2, 4, 5, 6, 10}, x = 2
Output: 3

Explanation: 2 occurs 3 times

Method 1 (Linear Search): The simplest way is to loop around the array and count the occurence of x. Time Complexity: O(n)

Method 2 (Binary Search): Use Binary search to get index of the first and last occurrence. Let the index of the first occurrence be i and the index of the last occurrence be j. The frequency of x is (j – i + 1).

#include<bits/stdc++.h>
using namespace std;

int countOccurence(int arr[], int x, int n)
{
    /* get the index of first occurrence of x */
    int *low = lower_bound(arr, arr+n, x);

    /* If element is not present, return 0 */
    if (low == (arr + n) || *low != x)
       return 0;

    /* get the index of last occurrence of x.
       we  are only looking in the subarray
       after first occurrence */
    int *high = upper_bound(low, arr+n, x);

    /* return count */
    return high - low;
}

/* driver function */
int main()
{
    int arr[] = {2, 2, 2, 4, 5, 6, 10};
    int x =  2;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << (" %d occurs %d times ", x, countOccurence(arr, x, n)) << endl;

    return 0;
}

Output:

3

Time Complexity: O(logn)