*2.4K*

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