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

Question

I am trying to use lower_bound and upper_bound functions from the algorithm library in C++ to find the following things:

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

I wrote the following code:

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

But for some random test cases it gives me wrong answer.

Can anyone find the incorrect piece of code in my program?

Answer 1

You've got the logic a bit backwards for the "smaller than or equal" case.

There are three cases you need to consider for the result of lower_bound: it returns the position after the last element, the position of the first element, or some position in between

If iter == ar+numElems, the value you're looking for is the last element of the array (because all elements are smaller than X).

If iter == ar (first position), there are two cases; *iter == X and *iter != X.
If *iter == X, X is your result because there are no smaller values in the array.
If *iter != X, the smallest array element is greater than X and you have no result.

Otherwise (that is, iter != ar) the result is ar[-1].