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 and Java implementation:

## C

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 69 70 |
#include <stdio.h> // 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, int 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(void) { int A[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int target = 5; int n = sizeof(A)/sizeof(A[0]); // pass value 1 for first occurrence int first = BinarySearch(A, n, target, 1); // pass value 0 for last occurrence int last = BinarySearch(A, n, target, 0); int count = last - first + 1; if (first != -1) printf("Element %d occurs %d times.", target, count); else printf("Element not found in the array."); return 0; } |

## Java

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 69 |
class BinarySearch { // If searchFirst is true, we return the first occurrence of a number // in sorted array of integers; else we return its last occurrence public static int binarySearch(int[] A, int x, boolean searchFirst) { // search space is A[left..right] int left = 0; int right = A.length - 1; // initialize the result by -1 int result = -1; // iterate till search space contains at-least one element while (left <= right) { // find the mid value in the search space and // compares it with key value int mid = (left + right) / 2; // if key is found, update the result if (x == A[mid]) { result = mid; // go on searching towards left (lefter indices) if (searchFirst) { right = mid - 1; } // go on searching towards right (higher indices) else { left = mid + 1; } } // if key is less than the mid element, discard right half else if (x < A[mid]) { right = mid - 1; } // if key is more than the mid element, discard left half else { left = mid + 1; } } // return the found index or -1 if the element is not found return result; } public static void main(String[] args) { int[] A = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9}; int key = 5; // pass true for first occurrence int first = binarySearch(A, key, true); // pass false for last occurrence int last = binarySearch(A, key, false); int c = last - first + 1; if (first != -1) { System.out.println("Element " + key + " occurs " + c + " times"); } else { System.out.println("Element not found in the array"); } } } |

`Output: `

Element 5 occurs 3 times

**Time complexity** of above solution 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 🙂