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

This video is contributed by Parikshit Kumar Pruthi

Please Like, Comment and Share the Video among your friends.

Also, Subscribe if you haven't already! :)

[ashwinirg]

iCreate a matrix of size 50×50 of numbers ranging from 0 to 9. Find the number of occurrences of 5 largest sorted components horizontally.

[clb]

What if we can’t sort the array prior to searching?

[lakhdeepsingh]

He just simply read what was written on the slides...

[Akshatmahla]

binary search has a bug. it should be else if(a[mid]<=x) in function first and last.

[atul]

y do u sound like a primary school teacher?

[wecan]

method



class Solution{
public:
/* if x is present in arr[] then returns the count
of occurrences of x, otherwise returns 0. */
int count(int arr[], int n, int x)
{
auto *it1 = lower_bound(arr, arr+n, x);

if(it1 == arr+n || (*it1) != x)
{
return 0;
}

auto *it2 = upper_bound(arr, arr+n, x);

return it2 - it1;

}
};




find first occurence and last occurence then find the result

refer -- aditya verma video

[coderajput]

your binary search code is wrong its correct code is

//sorted array
#include<stdio.h>
int firstOcc(int a[], int l, int h, int x)
{
if(l<=h)
{
int m=(l+h)/2;

return m;
else if(a[m]<x)
return firstOcc(a, m+1, h, x);
else
return firstOcc(a, l, m-1, x);
}
return -1;
}
int lastOcc(int a[], int l, int h, int x)
{
if(l<=h)
{
int m=(l+h)/2;

return m;
else if(a[m]>x)
return lastOcc(a, l, m-1, x);
else
return lastOcc(a, m+1, h, x);
}
return -1;
}
int count(int a[], int n, int x)
{
int r=firstOcc(a, 0, n-1, x);
if(r==-1)
return -1;
int j=lastOcc(a, 0, n-1, x);
return j-r+1;
}
int main()
{
int n;
scanf("%d", &n);
int a[n];
int i;
for(i=0;i<n;i++)
scanf("%d", &a[i]);
int x;
scanf("%d", &x);
int c=count(a, n, x);
printf("%d", c);
return 0;
}

[dustymiller]

Nicely done, short and to the point. Keep up the good work

[myth_un]

If the count is 0, It will return 1 ! thats an error