如何找到小于或等于 X 的最大值和大于或等于 X 的最小值？

Question

我正在尝试使用 C++ algorithm 库中的 lower_bound 和 upper_bound 函数来查找以下内容：

小于等于的最大值
大于等于的最小值

我写了下面的代码：

#include <iostream>
#include <algorithm>

int main() {

    using namespace std;

    int numElems;
    cin >> numElems;

    int ar[numElems];
    for (int i = 0; i < numElems; ++i)
        cin >> ar[i];
    stable_sort(ar,ar+numElems);

    cout << "Input number X to find the largest number samller than or equal to X\n";
    int X;
    cin >> X;

    int *iter = lower_bound(ar,ar+numElems,X);
    if (iter == ar+numElems)
        cout << "Sorry, no such number exists\n";
    else if (*iter != X && iter != ar)
        cout << *(iter-1) << endl;
    else 
        cout << *iter << endl;

    cout << "Input number X to find the smallest number greater than or equal to X\n";
    cin >> X;

    int *iter2 = lower_bound(ar,ar+numElems,X);
    if (iter2 == ar+numElems)
        cout << "Sorry, no such number exists\n";
    else
        cout << *iter2 << endl;

    return 0;   
}

但是对于一些随机测试用例，它给了我错误的答案。

有人能在我的程序中找到错误的代码吗？

Answer 1

让我告诉你哪里出错了：

int array[] = { 10, 15, 18 };

//Input number X to find the largest number samller than or equal to X

//X = 16
15 //Correct!

//X = 200
Sorry, no such number exists //Wrong! Should be 18

//X = 1
10 //Wrong! There is no such number

//Input number X to find the smallest number greater than or equal to X

//X = 16
18 //Correct!

//X = 200
Sorry, no such number exists //Correct!

//X = 1
10 //Correct!

如您所见，第一个测试用例是罪魁祸首，您错误地假设如果最后一个元素是最后一个元素之后的元素，则它没有找到该元素。但事实并非如此，因为最后一个元素总是是最小的！ 您应该删除条件。

接下来，对于第三个输入，你永远不会检查是否 iter == ar，但你应该检查，因为 iter == ar 当找到第一个元素时，如果不是 X，那么就没有这个数了（不可能是之前的那个，因为iter已经是第一个了！

Answer 2

对于 "smaller than or equal" 的情况，您的逻辑有点倒退。

lower_bound的结果需要考虑三种情况：returns最后一个元素之后的位置，第一个元素的位置，或者两者之间的某个位置

如果iter == ar+numElems，您要查找的值是数组的最后一个元素（因为所有元素都小于X）。

如果iter == ar（第一个位置），有两种情况； *iter == X 和 *iter != X.
如果 *iter == X，X 是您的结果，因为数组中没有更小的值。
如果*iter != X，最小的数组元素大于X，你没有结果。

否则（即iter != ar）结果为ar[-1].

Answer 3

The largest value smaller than or equal to a number X.

对我来说，排序数组最简单的方法是：

auto ret = upper_bound(arr.rbegin(), arr.rend(), X,
                       [](int a, int b){return a>=b;});

如何找到小于或等于 X 的最大值和大于或等于 X 的最小值？

How do I find the largest value smaller than or equal to X and the smallest value greater than or equal to X?

c++

algorithm

binary-search

divide-and-conquer