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

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:-

• Find the first occurrence of the element.
• Find the last occurrence of the element.
• Return (lastOccurrence – firstOccurrence + 1)

#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;
}