There is a given element say N. How to modify Binary Search to find greatest element in a sorted vector which smaller than N

Question

For example: Let us have a sorted vector with elements: [1, 3, 4, 6, 7, 10, 11, 13] And we have an element N = 5

I want output as:

4

Since 4 is the greatest element smaller than N.

I want to modify Binary Search to get the answer

Answer 1

What would you want to happen if there is an element that equals N in the vector?

I would use std::lower_bound (or std::upper_bound depending on the answer to the above question). It runs in logarithmic time which means it's probably using binary search under the hood.

std::optional<int> find_first_less_than(int n, std::vector<int> data) {
    // things must be sorted before processing
    std::sort(data.begin(), data.end());

    auto it = std::lower_bound(data.begin(), data.end(), n);

    // if all of the elements are above N, we'll return nullopt
    if (it == data.begin()) return std::nullopt;

    return *std::prev(it);
}