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