Count the number of occurrences in a sorted Array

Approach to finding the number of occurrences(using binary search)

We can use binary search to find the number of occurrences in a sorted array.This is a better approach and a very common application of binary search.

Implementation in C++

#include<iostream>
using namespace std;

int binarySearch(int a[], int l, int r, int x)
{
    if (r < l)
        return -1;
 
    int mid = l + (r - l) / 2;
 
    if (a[mid] == x)
        return mid;

    if (a[mid] > x)
        return binarySearch(a, l, mid - 1, x);

    return binarySearch(a, mid + 1, r, x);
}
 
int countOccurrences(int a[], int n, int x)
{
    int ind = binarySearch(a, 0, n - 1, x);

    if (ind == -1)
        return 0;

    int count = 1;
    int left = ind - 1;
    while (left >= 0 && a[left] == x)
        count++, left--;
 
    int right = ind + 1;
    while (right < n && a[right] == x)
        count++, right++;
 
    return count;
}
 
// Driver code
int main()
{
    int a[] = { 4,5,6,6,9,9,11,11,11,13,13};
    int n = sizeof(a) / sizeof(a[0]);
    int x = 11;
    cout << countOccurrences(a, n, x);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

3

Complexity Analysis

Time complexity: O(log n+count)

Space complexity: O(n)

Also Read - Selection Sort in C

Approach to finding the number of occurrences(using improved binary search)

This is the best approach to find the number of occurrences.The approach to this method is simple:

• In this method, first we will get the index of the first occurrence of the number in array[] using binary search.Let its index be x.
• Now we will find the index of last occurrence of the number in array[]  using binary search method.Let this be denoted by y
• So number of occurrences will be y-x+1.

Implementation in C++

# include <bits/stdc++.h>
using namespace std;
 
int count(int a[], int x, int n)
{   
  int *low = lower_bound(a, a+n, x);
 
  if (low == (a + n) || *low != x)
     return 0;
    
  int *high = upper_bound(low, a+n, x);    

  return high - low;
}


int main()
{
  int a[] = {2,5,6,6,7,8,9,9,9,10,11};
  int x =  9;  
  int n = sizeof(a)/sizeof(a[0]);
  int c = count(a, x, n);
  cout<<x<<" occurs "<<c <<" times in the array"<<endl;
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

9 occurs 3 times in the array

You can try by yourself with the help of online C++ Compiler.

Complexity Analysis

Time complexity: O(log n)

Space complexity:O(n)

Also Read - Strong number in c

Frequently Asked Questions

1. What is sizeof() function in c++?
   It is a function that returns the size of a data type like an array, expression, etc., in c++.for an array, it will return the number of elements in that array.
    
2. Name some sorting techniques used in c++?
   Some of the most used sorting techniques are:
   → Bubble sort
   → Selection sort 
   → Quick sort
   → Merge sort
   → Heap sort
   → Shell sort
   → Insertion sort
    
3. What is a class in c++?
   A class defines a datatype, and provide set of operations, and databits.Its is also used in c language .

Conclusion

In this blog, we discussed how to find the number of occurrences in a sorted array. We then looked at linear search and binary search approach to this problem. We discussed time complexity and space complexity of this problem.We hope that this blog has helped you enhance your knowledge regarding program to count number of occurrences in a sorted array and if you would like to learn more, check out our articles on C++. 

Recommended problems -

• Product Array Puzzle
• Beautiful Array

Also read -  Decimal to Binary c++

Do upvote our blog to help other ninjas grow. Happy Coding!”