If the array is sorted, then the frequency of any element can be found easily by using binary search.
Suppose you have a sorted array
a = [ 1, 3, 3, 5. 6, 6, 8, 9 ]
and you want to find the frequency of 6. Frequency is the number of times the element occurs here the frequency of 6 is 2 as 6 appears 2 times in the array.
LINEAR SEARCH APPROACH :
Ofcourse the most common approach for finding the frequency of an element in an array is to iterate over the array and each time a match is found, the count can be increased.
This works wll if the array is unsorted. But what if the array is sorted? Can we do better than O( n ). YES! and this is where binary search comes into play.
BINARY SEARCH APPROACH :
The first step is to find if the required element is present in the array.
#include
using namespace std;
int main(){
int arr[] = { 1, 3, 3, 5, 6, 6, 8, 9 };
bool found = binary_search( arr , arr+8 ,6 );
cout << found << endl;
}
We will be using the library which provides us with all the necessary functions and IO. We will also use the built in binary search methods to prevent writing our own.
The binary_search function of the std library takes in 3 arguments
- The start address of array
- The end address of array
- The element to search
It returns a boolean value. 1 if the element is present and 0 if the element is not present. So the output of the above code will be
1
The next step is to use the lower_bound and upper_bound functions. They both take the same argument as binary_search.
The lower_bound function returns an iterator pointing to the smallest element that is equal to or greater than (=>) the element to be found.
The lower_bound function returns an iterator pointing to the smallest element that is strictly greater than (>) the element to be found.
upper_bound-lower_bound = frequency of the element
So the final code will be
#include
using namespace std;
int main(){
int arr[] = { 1, 3, 3, 5, 6, 6, 8, 9 };
bool found = binary_search( arr , arr+8 ,6 );
if(found){
auto ub=upper_bound( arr , arr+8 ,6 );
auto lb=lower_bound( arr , arr+8 ,6 );
cout << "The frequency of 6 is : "<<(ub-lb)<
}
else{
cout<<"Element not present in array"<
}
}
OUTPUT :
The frequency of 6 is : 2
0 Comments
Leave a Comment