Home Arrays Find the number of occurrences of an element in a sorted array. (Method 2)

# Find the number of occurrences of an element in a sorted array. (Method 2)

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

We discussed the basic method to find the number of occurrences in this post. But here, in both the cases, the time complexity is not good. We can use some of the tricks studied earlier to find a time efficient method. What we can do is:-

#include<stdio.h>

int binarySearchFirstOccurrence(int arr[], int low, int high, int data)
{
int mid;
if(high >= low)
{
mid = low + (high - low)/2;	// To avoid overflow
if((mid == low && arr[mid] == data) || (arr[mid] == data && arr[mid-1] < data))
return mid;
else if(arr[mid] >= data)
return binarySearchFirstOccurrence(arr, low, mid-1, data);
else
return binarySearchFirstOccurrence(arr, mid+1, high, data);
}
}

int getFirstOccurrence(int arr, int len, int data)
{
int low = 0, high = len - 1;
int index = binarySearchFirstOccurrence(arr, low, high, data);
return index;
}

int binarySearchLastOccurrence(int arr[], int low, int high, int data)
{
int mid;
if(high >= low)
{
mid = low + (high - low)/2; // To avoid overflow
if((mid == high && arr[mid] == data) || (arr[mid] == data && arr[mid+1] > data))
return mid;
else if(arr[mid] <= data)
return binarySearchLastOccurrence(arr, mid+1, high, data);
else
return binarySearchLastOccurrence(arr, low, mid-1, data);
}
}

int getLastOccurrence(int arr, int len, int data)
{
int low = 0, high = len - 1;
int index = binarySearchLastOccurrence(arr, low, high, data);
return index;
}

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

int firstOccurrence = getFirstOccurrence(arr, 11, 8);
int lastOccurrence = getLastOccurrence(arr, 11, 8);
int count = lastOccurrence - firstOccurrence + 1;

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

return 0;
}

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