时间戳

首页 > 解决方案 > 如何使用upper_bound找出满足某个条件的最后一个变量

c++ - 如何使用upper_bound找出满足某个条件的最后一个变量

问题描述

我正在尝试使用 log(n) 方法来找出满足特定条件的最后一个变量。我查看了文档并在算法部分找到了这些（http://www.cplusplus.com/reference/algorithm/）

二分搜索（在分区/排序范围上操作）：

lower_bound：将迭代器返回到下限（函数模板）

upper_bound：将迭代器返回到上限（函数模板）

equal_range：获取相等元素的子范围（函数模板）

binary_search：测试排序序列中是否存在值（函数模板）

我认为要做我想做的事，我应该使用upper_bound/lower_bound。

在这种情况下，我试图找出小于或等于 3 的数字的最后一个索引。 (3)。我知道有更简单的方法，例如遍历整个数组，但我想学习如何使用 upper_bound。我知道比较器需要 2 个数字，但我不需要 2 个数字，所以我不知道该怎么做。

#include <bits/stdc++.h>

using namespace std;
vector<int> a = {0,1,2,3,4,5};
bool check(int base) {
    if (a.at(base)  <= 3) {
        return true;
    }
    return false;
}

int main() {
    int c;
    sort(a.begin(), a.end());
    c = distance(a.begin(), upper_bound(a.begin(), a.end(), check));
    cout<<c;
    return 0;
}

我将如何正确地做到这一点？

标签： c++c++11c++14c++17

解决方案

比较器将您正在搜索3的数字与向量中的数字进行比较。这就是为什么它需要两个参数。当您3应该将它作为参数传递给upper_bound.

它也是对向量进行排序的函数，所以如果你要使用一个，你也应该将它传递给sort.

您的代码可能如下所示

bool check(int x, int y) {
    return x < y;
}

int main() {
    int c;
    sort(a.begin(), a.end(), check);
    c = distance(a.begin(), upper_bound(a.begin(), a.end(), 3, check));
}

但由于在这种情况下check只是默认的小于操作，您可以完全忽略它。

int main() {
    int c;
    sort(a.begin(), a.end());
    c = distance(a.begin(), upper_bound(a.begin(), a.end(), 3));
}

请参阅此处的参考

推荐阅读