有一个给定的元素说 N。如何修改二进制搜索以找到小于 N 的排序向量中的最大元素

Question

例如：让我们有一个包含元素的排序向量：[1, 3, 4, 6, 7, 10, 11, 13] 我们有一个元素 N = 5

我希望输出为：

因为4是小于N的最大元素

我要修改二分查找得到答案

Answer 1

如果向量中有一个等于 N 的元素，您希望发生什么？

我会使用 std::lower_bound（或 std::upper_bound，具体取决于对上述问题的回答）。它以对数时间运行，这意味着它可能在后台使用二进制搜索。

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);
}

有一个给定的元素说 N。如何修改二进制搜索以找到小于 N 的排序向量中的最大元素

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

c++

vector

binary-search

c++-standard-library