Given a sorted array of numbers, How to find the frequency of a given number?

Here is an efficient algorithm to do it. Use binary search to find the left-most(L), and right-most(R) occurrence of the given number. Then R-L+1 gives us the result.

C++ STL has two functions namely lower_bound, upper_bound which finds out the left-most and right-most occurrences of a given number in a sorted array.

The lower_bound() function returns an iterator to the left-most element, and the upper_bound() function returns an iterator to one element beyond right-most occurrence. So the difference of these two gives the count.

Here is the C++ code.

#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int getCount(vector<int> & numVector, int d) { int result = 0; vector<int>::iterator left, right; //find the left-most occurence left = lower_bound( numVector.begin(), numVector.end(), d ); //find right-most occurence only if the number is present if( left != numVector.end() ) { right = upper_bound( numVector.begin(), numVector.end(), d ); result = right-left; //right points to one element beyond. } return result; } int main() { int n; //read array size cin>>n; int i,num; vector<int> nums; //read the array for( i = 0 ; i < n ; i++ ) { cin>>num; nums.push_back(num); } //read the number to be counted cin>>num; cout<<getCount(nums,num); return 0; }