Count Numbers Less Than in a Sorted Vector using Binary Search (C++)

Implement a function countNumbers that accepts a sorted vector of unique numbers (integers), and efficiently with respect to time used, counts the number of vector elements that are less than the parameter lessThan.

For example, in sorted vector {1, 3, 5, 7}, and lessThan is 4, the function countNumber should return 2 i.e. there are two elements which are less than 4.

Since the vector contains sorted and unique integers, we can first locate the number using binary search with O(logN) complexity. If the number is located, great, then we know easily how many numbers that is smaller than the number as we know the index.

If the number cannot be located, at least we know it is between low and high range – then we have to compare the number with the lower end. There are two possible answers that differ by one exactly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <vector>
#include <stdexcept>
#include <iostream>
 
class SortedSearch
{
public:
    static int countNumbers(const std::vector<int>& sortedVector, int lessThan)
    {
        int low = 0, high = sortedVector.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int v = sortedVector[mid];            
            if (lessThan < v) {
                high = mid - 1;
            } else if (lessThan > v) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return ((lessThan == sortedVector[low]) ? low - 1: low);
    }
};
 
#ifndef RunTests
int main()
{
    std::vector<int> v { 1, 3, 5, 7 };
    std::cout << SortedSearch::countNumbers(v, 4);
}
#endif

#include <vector>
#include <stdexcept>
#include <iostream>

class SortedSearch
{
public:
    static int countNumbers(const std::vector<int>& sortedVector, int lessThan)
    {
        int low = 0, high = sortedVector.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int v = sortedVector[mid];            
            if (lessThan < v) {
                high = mid - 1;
            } else if (lessThan > v) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return ((lessThan == sortedVector[low]) ? low - 1: low);
    }
};

#ifndef RunTests
int main()
{
    std::vector<int> v { 1, 3, 5, 7 };
    std::cout << SortedSearch::countNumbers(v, 4);
}
#endif

Overall, the sorted characteristics bring down the complexity from O(n) to O(logN).

–EOF (The Ultimate Computing & Technology Blog) —