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

# 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

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More