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.

0 comment

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

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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