Given a sorted array of integers containing duplicates, count occurrences of a number provided. If the element is not found in the array, report that as well.

For example,

**Input: **A[] = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]

target = 5

** Output: **Element 5 occurs 3 times

**Input: **A[] = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]

target = 6

** Output: **Element 6 occurs 2 times

A simple solution would be to run a linear search on the array and count number of occurrence of the given element. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is sorted.

Another solution would be to run a binary search on given sorted array and find the index of any occurrence of given number. Since the array is sorted, all occurrences of given element will be adjacent. So, we run a linear scan to find all instances of given element to the left of found index and also to its right. The worst case time complexity of this solution would remain O(n). The worst case happen when all elements of the array is same as the given element.

We can easily solve this problem in O(log(n)) time by **modifying binary search algorithm**. The idea is to find the index of first and last occurrence of given number and return the difference between two indices + 1. We have already discuss how to find first and last occurrence of given number in O(log(n)) time in previous post.

Below is its C++ implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> using namespace std; // Function to find first or last occurrence of a given number in // sorted array of integers. If searchFirst is true, we return the // first occurrence of the number else we return its last occurrence int BinarySearch(int A[], int N, int x, bool searchFirst) { // search space is A[low..high] int low = 0, high = N - 1; // initialize the result by -1 int result = -1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // if target is found, update the result if (x == A[mid]) { result = mid; // go on searching towards left (lower indices) if (searchFirst) high = mid - 1; // go on searching towards right (higher indices) else low = mid + 1; } // if target is less than the mid element, discard right half else if (x < A[mid]) high = mid - 1; // if target is more than the mid element, discard left half else low = mid + 1; } // return the found index or -1 if the element is not found return result; } // Count occurrences of a number in a sorted array with duplicates int main() { int A[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int n = sizeof(A)/sizeof(A[0]); int target = 5; int first = BinarySearch(A, n, target, 1); // 1 for first occurrence int last = BinarySearch(A, n, target, 0); // 0 for last occurrence int count = last - first + 1; if (first != -1) cout << "Element " << target << " occurs " << count << " times"; else cout << "Element not found in the array"; return 0; } |

`Output: `

Element 5 occurs 3 times

**Time complexity** of above solutions is O(log(n)).

**Auxiliary space** used by the program is O(1).

**Related post: **Find first or last occurrence of given number in a sorted array

**References:**

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Hi there, You guys are doing an excellent job.

I would like to correct a small typo mistakes.

As given example

Input: A[] = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]

target = 3

Output: Element 6 occurs 2 times

here , target should be 6 instead of 3.

Happy coding !

Thanks Abdullah for your kind words and bringing this typo into our notice. We have corrected it. Thanks again and happy coding 🙂