Find the number of occurrences of an element in a sorted array.

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element.

Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8
Output: Count = 3

The most basic methodology to solve this problem is linear search. Just scan the array and count the number of occurrences. But this takes time O(n).

int linearSearchCount(int arr[], int n, int data)
{
	int count = 0;
	int i = 0;

	for(i=0;i<n;i++)
	{
		if(arr[i] == data)
			count++;
	}

	return count;
}

We can improve the time complexity by using binary search. The steps involved in this method are:-

• Do a binary search and search for the data in the array. Let us assume that the position is K.
• Now traverse left from the position K, until we get a different element. Keep a count of the number of elements. Let it be leftCount.
• Now traverse right from the position K, until we get a different element. Keep a count of the number of elements. Let it be rightCount.
• Total number of occurrences = leftCount + 1 + rightCount

#include<stdio.h>

int binarySearchIterative(int arr[], int size, int data)
{
	int low = 0;
	int high = size-1;
	int mid;
	while(low<=high)
	{
		mid = low + (high-low)/2;
		if(arr[mid] == data)
			return mid;
		else
			if(arr[mid] < data)
				low = mid + 1;
			else
				high = mid - 1;
	}
	return -1;
}

int binarySearchCount(int arr[], int len, int data)
{
	// get the index of element
	int indexData = binarySearchIterative(arr, len, data);

	// get the leftCount
	int left = indexData - 1;
	int leftCount = 0;
	while(left>-1 && arr[left] == data)
	{
		leftCount++;
		left--;
	}

	// get the rightCount
	int right = indexData + 1;
	int rightCount = 0;
	while(right < len && arr[right] == data)
	{
		rightCount++;
		right++;
	}

	return (leftCount + 1 + rightCount);
}

int main(void)
{
	int arr[] = {4, 4, 8, 8, 8, 15, 15, 16, 23, 42, 42};

	int count = binarySearchCount(arr, 11, 8);

	printf("count = %d", count);

	return 0;
}

Time Complexity:- O(log n + S), where S is the number of occurrences