c++arraysalgorithmstdvector

How to find closest smaller number in array?


Consider this array:

std::vector<int> numbers = { 0, 4, 12, 60, 89 };

It is sorted and only has positive numbers.

What is the easiest way to find the closest smaller number in the array, preferably from <algorithm>? Example:

Number Result
0 0
3 0
15 12
74 60
150 89

Solution

  • What is the easiest way to find the closest smaller number in the array, preferably from <algorithm>?

    One could make use of the already existing std::lower_bound (or std::ranges::lower_bound since C++20) for this. Check the example code given on the referenced pages.

    For example, you could write a function as follows. I leave the error handling as well as corner cases perfections for you.

    #include <algorithm>  // std::ranges::lower_bound
    
    constexpr auto find_equal_or_closest(std::vector<int> const& numbers, const int query)
    {
        // invalid query/ not able to find cases!
        // you could also restructure to return std::cend(numbers) from function.
        if (numbers.empty() 
            /* || !std::ranges::is_sorted(numbers) */ // optional check
            || query < *std::cbegin(numbers)
            )       
            return -1; 
    
        auto it = std::ranges::lower_bound(numbers, query);
        return (it != std::cend(numbers) && *it == query) ? *it : *std::prev(it);
    }
    

    See live demo