Given a sorted list of integers with duplicates, find the count of a given number in this list in O(log n).
InputFirst line of input will contain a positive integer T = number of test cases. Each test case will contain 2 lines. First line of each test case will contain two number N = number of elements in list and K separated by space. Next line will contain N space separated integers.
OutputFor each test case, print on a single line, the count of number K in this list.
Sample Input3 10 5 1 2 2 5 5 5 7 7 7 8 10 1 1 1 1 1 1 1 1 2 2 3 20 2 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4Sample Output
3 7 5
Here the array is sorted. So, duplicate values will be placed continuously. So, we just need to find the first and last occurrence of the desired number. The answer will be the difference of the position of last occurrence and the position of first occurrence.
We can do this in two ways:-
The function
binary_search_high(int num)calculates the highest position of the required number in
O(log n)
time.The function
binary_search_low(int num)calculates the lowest position of the required number in O(logn) time.
Now, the number of times the required number is in the array is highest_position - lowest_position + 1.
This can also be solved by simple use of STL.
The position of first occurrence of a number in a sorted list can be calculate with the help of binary search in just O(log n) time. The function 'lower_bound' in C++ provides this functionality (almost). We use the function in this manner:-
lower_bound(arr, arr + n, number)Here
arr
is the array where the numbers are stored.n
is the number of elements in it. number
is the number whose lower_bound we are trying to find. This function will return the maximum position where a number just smaller than the given number
can be placed such that the array remains sorted even after the insertion. If the number
is the smallest number then an iterator to the first position of the array will be returned. Check this link for better understanding.
The position of last occurrence of a number in a sorted list can be calculated with the help of binary search in just O(log n) time. The function 'upper_bound' in C++ provides this functionality (almost). We use the function in this manner:-
upper_bound(arr, arr + n, number)Here
arr
is the array where the numbers are stored.n
is the number of elements in it. number
is the number whose upper_bound we are trying to find. This function will return the minimum position where a number just greater than the given number
can be placed such that the array remains sorted even after the insertion. If the number
is the largest number then an iterator to the last position of the array will be returned. Check this link for better understanding.
We can calculate the the number of desired elements by simply finding the difference between the upper_bound and the lower_bound in the following way:-
cout << (upper_bound(arr, arr+n, num) - lower_bound(arr, arr+n, num));This will print the desired value.
editorial written by i_coder
#include<iostream> #include<cstdio> #include<cmath> #include <algorithm> using namespace std; int a[10000]; int test, num, n; /* int solve_by_STL(int num) { //Print the difference in position between the first and //the last occurence of the desired number using //inbuilt functions. These functions calculate the result //in O(log n) time complexity. return (upper_bound(a, a+n, num) - lower_bound(a, a+n, num)); } */ //Search the highest position of the number int binary_search_high(int num) { //set high to the largest value int high = n; // set low to the lowest possible value int low = -1; int mid, ans = 0; while(low+1<high){ //mid is the middle of high and low mid = (high + low) / 2; /*If the number at the current position is less than or equal to the requied number, then there is a possibility of having the number in the upper part of the array. So, we make low = mid. */ if(a[mid] <= num){ low = mid; /* Else we need to search for the required number in the lower part of the array. So we make high = mid. */ } else { high = mid; } } return low; } //Find the lowest position of the number int binary_search_low(int num) { //set high to the largest value int high = n; // set low to the lowest possible value int low = -1; int mid, ans = 0; while(low + 1 < high){ //mid id the middle of high and low mid = (high + low) / 2; /*If the number at the current position is greater than or equal to the requied number, then there is a possibility of having the number in the lower part of the array. So, we make high = mid. */ if(a[mid] >= num){ high = mid; /* Else we need to search for the required number in the upper part of the array. So we make low = mid. */ } else { low = mid; } } return high; } int main() { cin >> test; while(test--){ //Take input the number of elements and the desired number. cin >> n >> num; for(int i = 0; i < n; i++){ cin >> a[i]; } //To solve by STL run this:- /* solve_by_STL(num) */ //To solve by simple binary search :- cout << binary_search_high(num) - binary_search_low(num) + 1 << endl; } }
featured solution by i_coder