ADVERTISEMENT
ADVERTISEMENT

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

In this article, we are going to see how to find the number of occurrences for any given element in a sorted array?
Submitted by Radib Kar, on February 03, 2021

For example,

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.

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

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:

#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
ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.