Home » Algorithms

Count number of occurrences (or frequency) in a sorted array

In this tutorial, we will learn how to find the number of occurrences for any given element in a sorted array using C++ program? By Radib Kar Last updated : August 10, 2023

Problem statement

If the array is [2,3,3,4,5,6,6,6,6,7] and if the element is 6 then it has frequency 4.

We can solve this by either using the linear search or binary search.

Count number of occurrences in a sorted array using linear search

Keep searching elements by elements until you find the given element. Once you find the given element keep incrementing the frequency count until you meet any other value. Since the array is sorted it's guaranteed there won't be any other occurrence of this element after that. Below is the code snippet for reference. This has a time complexity of O(n).

void findFrequencyeNaive(vector& arr, int num)
{
    cout << "..............Using naive search......\n";

    //O(n) time complexity

    int freq = 0;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] > num)
            break;
        if (arr[i] == num)
            freq++;
    }
    if (freq == 0)
        cout << "No such occurences found";
    else
        cout << "Frequency of given element  " << d << " is:  " << freq << "\n";

    return;
}

Count number of occurrences in a sorted array using binary search

We can also use a binary search. Using binary search we need o find two things, one is the first occurrence of the element and another is the last occurrence of the element.

Below is the code snippe for finding fast & last occurrence using binary search. The frequency count would be last occurrence index - first occurrence index +1.

//code snippet to find first occurence
int first_occurence(vector& arr, int d)
{
    int start = 0, end = arr.size() - 1;
    int index = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == d) {
            index = mid;
            end = mid - 1;
        }
        else if (arr[mid] > d) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return index;
}
//code snippet to find the last occurrence

int last_occurence(vector& arr, int d)
{
    int start = 0, end = arr.size() - 1;
    int index = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == d) {
            index = mid;
            start = mid + 1;
        }
        else if (arr[mid] > d) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return index;
}

C++ program to count number of occurrences (or frequency) in a sorted array

#include <bits/stdc++.h>
using namespace std;

//naive approach
void findFrequencyeNaive(vector<int>& arr, int num)
{
    int d;
    
    cout << "..............Using naive search......\n";

    //O(n) time complexity

    int freq = 0;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] > num)
            break;
        if (arr[i] == num)
            freq++;
    }
    if (freq == 0)
        cout << "No such occurences found";
    else
        cout << "Frequency of given element  " << d << " is:  " << freq << "\n";

    return;
}

//function to find first occurence
int first_occurence(vector<int>& arr, int d)
{
    int start = 0, end = arr.size() - 1;
    int index = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == d) {
            index = mid;
            end = mid - 1;
        }
        else if (arr[mid] > d) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return index;
}

//function to find last occurence

int last_occurence(vector<int>& arr, int d)
{
    int start = 0, end = arr.size() - 1;
    int index = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == d) {
            index = mid;
            start = mid + 1;
        }
        else if (arr[mid] > d) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return index;
}

void findFrequencyEfficient(vector<int>& arr, int d)
{

    cout << "..............Using efficient approach(binary search)......\n";

    //O(logn) time complexity

    //find out tyhe first occurence

    int first_index = first_occurence(arr, d);
    if (first_index == -1) {
        cout << "No such occurences found";
        return;
    }
    int last_index = last_occurence(arr, d);

    int freq = last_index - first_index + 1;
    cout << "Frequency of given element  " << d << " is:  " << freq << "\n";
}

int main()
{
    cout << "Enter number of elements\n";
    int n;
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements\n";

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << "Enter the element\n";
    int d;
    cin >> d;

    //using navive approach
    findFrequencyeNaive(arr, d);
    //using binary search
    findFrequencyEfficient(arr, d);

    return 0;
}

Output

Enter number of elements
10
Enter the elements
2 3 3 4 4 6 6 6 6 7
Enter the element
6
..............Using naive search......
Frequency of given element 6 is: 4
..............Using efficient approach(binary search)......
Frequency of given element 6 is   : 4