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.

by nikoo28
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

Enclose codes in [code lang="JAVA"] [/code] tags

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