# Count Occurrences in Sorted Array

Problem: Given a sorted array and an element x, we need to count occurrences of x in the array.

Examples:

``````Input:arr[] = {10, 20, 20, 20, 30, 30}, x = 20
Output: 3

Input: arr[] = {10, 10, 10, 10, 10}, x = 10
Output: 5

Input: arr[] = {5, 8, 10}, x = 7
Output: 0``````

Naive solution is to traverse array linearly by maintaining count for the given element which has a time complexity of O(n)

Efficient solution is to make use of two Binary Search (Index of First Occurrence + Index of Last Occurrence) implementations which has a time complexity O(log n) for each which is equal to O(log n)

Here are the links implementations for Index of First and Last Occurence:

Index of First Occurrence in Sorted Array

Index of Last Occurrence in Sorted Array

Solution:

``````/**
* <p><b>Count Occurrences:</b> is to count occurrences of given element in an array or list</p>
* <p><b>Time Complexity:</b> O(log n)</p>
* <p><b>Usage:</b></p>
* {@code
* int[] countOccNums = {10, 10, 20, 30};
* CountOccurrences.of(countOccNums, 10)
* }
*/
public class CountOccurrences {

/**
* <b>FLow:</b>
* <p>Make use of two Binary Search (Index of First Occurrence + Index of Last Occurrence)
* implementations</p>
* @param arr integer array
* @param x element to find count for
* @return total count for given element
*/
public static int of(int[] arr, int x) {
int first = FirstOccurrence.of(arr, x);

if (first == -1) return 0;
else return LastOccurrence.of(arr, x) - first + 1;
}
}``````