Monday, May 6, 2013

Finding count of a number in a sorted array

In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.
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;
}