Как найти наибольшее значение, меньшее или равное X, и наименьшее значение, большее или равное X?

Question

Я пытаюсь использовать lower_bound и upper_bound функции из algorithm библиотеки в C++, чтобы найти следующие вещи:

• наибольшее значение меньше или равно к числу X.
• наименьшее значение, большее или равное к числу X.

Я написал следующий код:

#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

у вас есть логика немного назад для «меньше или равно» случае.

есть три случая, которые необходимо учитывать для результата из lower_bound: он возвращает позицию после последнего элемента, положение первого элемента или некоторую позицию в между

Если значение iter == ar+numElems, то значение, которое вы ищете, является последним элементом массива (поскольку все элементы меньше X).

Если iter == ar (первая позиция), возможны два случая; *iter == X и *iter != X.
Если *iter == X, X - ваш результат, поскольку в массиве нет меньших значений.
Если номер *iter != X, самый маленький элемент массива больше X, и у вас нет результата.

В противном случае (то есть iter != ar) результатом является ar[-1].

Answer 2

Позвольте мне показать вам, где вы сделали некоторые ошибки:

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 это уже первый один!