# Count number of occurrences (or frequency) in a sorted array

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)

Examples:

```  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
Output: 4 // x (or 2) occurs 4 times in arr[]

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 3
Output: 1

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 1
Output: 2

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 4
Output: -1 // 4 doesn't occur in arr[]```

Method 1 (Linear Search)
Linearly search for x, count the occurrences of x and return the count.

`// C++ program to count occurrences of an element`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns number of times x occurs in arr[0..n-1]`
`int` `countOccurrences(``int` `arr[], ``int` `n, ``int` `x)`
`{`
`    ``int` `res = 0;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``if` `(x == arr[i])`
`          ``res++;`
`    ``return` `res;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `arr[] = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``int` `x = 2;`
`    ``cout << countOccurrences(arr, n, x);`
`    ``return` `0;`
`}`

Output :

`4`

Time Complexity: O(n)

Method 2 (Use Binary Search)
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);

`/* if x is present in arr[] then returns the count of occurrences of x, `
`   ``otherwise returns -1. */`
`int` `count(``int` `arr[], ``int` `x, ``int` `n)`
`{`
`  ``int` `i; ``// index of first occurrence of x in arr[0..n-1]`
`  ``int` `j; ``// index of last occurrence of x in arr[0..n-1]`
`    `
`  ``/* get the index of first occurrence of x */`
`  ``i = first(arr, 0, n-1, x, n);`
`  ``/* If x doesn't exist in arr[] then return -1 */`
`  ``if``(i == -1)`
`    ``return` `i;`
`   `
`  ``/* Else get the index of last occurrence of x. Note that we `
`      ``are only looking in the subarray after first occurrence */`
`  ``j = last(arr, i, n-1, x, n);     `
`   `
`  ``/* return count */`
`  ``return` `j-i+1;`
`}`
`/* if x is present in arr[] then returns the index of FIRST occurrence `
`   ``of x in arr[0..n-1], otherwise returns -1 */`
`int` `first(``int` `arr[], ``int` `low, ``int` `high, ``int` `x, ``int` `n)`
`{`
`  ``if``(high >= low)`
`  ``{`
`    ``int` `mid = (low + high)/2;  ``/*low + (high - low)/2;*/`
`    ``if``( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)`
`      ``return` `mid;`
`    ``else` `if``(x > arr[mid])`
`      ``return` `first(arr, (mid + 1), high, x, n);`
`    ``else`
`      ``return` `first(arr, low, (mid -1), x, n);`
`  ``}`
`  ``return` `-1;`
`}`
`/* if x is present in arr[] then returns the index of LAST occurrence `
`   ``of x in arr[0..n-1], otherwise returns -1 */`
`int` `last(``int` `arr[], ``int` `low, ``int` `high, ``int` `x, ``int` `n)`
`{`
`  ``if``(high >= low)`
`  ``{`
`    ``int` `mid = (low + high)/2;  ``/*low + (high - low)/2;*/`
`    ``if``( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )`
`      ``return` `mid;`
`    ``else` `if``(x < arr[mid])`
`      ``return` `last(arr, low, (mid -1), x, n);`
`    ``else`
`      ``return` `last(arr, (mid + 1), high, x, n);      `
`  ``}`
`  ``return` `-1;`
`}`
`/* driver program to test above functions */`
`int` `main()`
`{`
`  ``int` `arr[] = {1, 2, 2, 3, 3, 3, 3};`
`  ``int` `x =  3;  ``// Element to be counted in arr[]`
`  ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`  ``int` `c = count(arr, x, n);`
`  ``printf``(``" %d occurs %d times "``, x, c);`
`  ``getchar``();`
`  ``return` `0;`
`}`

Output:

```3 occurs 4 times
```

Time Complexity: O(Logn)