Part 19 of 22 in Binary Search  

Find count of a number in a sorted list with duplicates by animeshn

Problem statement

Given a sorted list of integers with duplicates, find the count of a given number in this list in O(log n).

Input

First 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.

Output

For each test case, print on a single line, the count of number K in this list.

Sample Input
3
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 4
Sample 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:-

  1. Simple Binary search.

    The function

     binary_search_high(int num) 
    calculates the highest position of the required number in O(log n) time.
    If the number at the current position is less than or equal to the required number, then there is a possibility of having the number in the upper part of the array. So, we make low = mid. Else, if the number at the current position is less than number, we need to search for the required number in the lower part of the array. So we make high = mid.

    The function

     binary_search_low(int num) 
    calculates the lowest position of the required number in O(logn) time.
    If the number at the current position is greater than or equal to the required number, then there is a possibility of having the number in the lower part of the array. So, we make high = mid. Else, if the number at the current position is less than number, we need to search for the required number in the upper part of the array. So we make low = mid.

    Now, the number of times the required number is in the array is highest_position - lowest_position + 1.

  2. 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.

  3. 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



To try out your code



Sign in

Sign up