CODEWITHSUNDEEP
c++algorithmbinary-searchdivide-and-conquer
Deepam Sarmah
Deepam Sarmah

Reputation: 155

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

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

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?

Upvotes: 4

Views: 6436

Answers (3)

Albert
Albert

Reputation: 123

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

For me the easiest way for sorted array is:

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

Upvotes: 5

molbdnilo
molbdnilo

Reputation: 66371

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].

Upvotes: 1

Rakete1111
Rakete1111

Reputation: 48958

Let me show you where you made some errors:

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!

As you can see, the first test case is the culprit, you falsely assume that if the last element is one past the last element, that it didn't find the element. But that's never the case, because the last element will always be the smallest one! You should remove the condition.

Next, for the third input, you never check if iter == ar, but you should, because iter == ar when the first element is found, and if it is not X, then there is no such number (it can't be the one before, because iter is already the first one!

Upvotes: 1

Related Questions