*866*

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