ronith
6/8/2018 - 6:17 AM

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

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)

Examples:

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 2 Output: 4 // x (or 2) occurs 4 times in arr[]

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 3 Output: 1

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 1 Output: 2

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 4 Output: -1 // 4 doesn't occur in arr[]

Count number of occurrences or frequency in a sorted array.cpp
content_copyfile_download
#include<iostream>
using namespace std;

int binary(int a[],int l,int r,int x){
    if(l<=r){ //using binary search
        int m=(l+r)/2;
        if (a[m]==x)
            return 1+binary(a,l,m-1,x)+binary(a,m+1,r,x);
        if (a[m]>x)
            return binary(a,l,m-1,x);
        return binary(a,m+1,r,x);
    }
    return 0;
}

int main(){
    int n,x;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>x;

    int count=binary(a,0,n-1,x);
    cout<<"Frequency is: "<<count;
}