Не могу понять функцию с нижней границей с помощью компаратора

#c #stl #lower-bound

#c #stl #нижняя граница

Вопрос:

Я не могу понять, почему я получаю результат 200, тогда как, создав свою собственную функцию сравнения, я изменил условия, и результат должен быть 100.

 #include <iostream>
#include <algorithm>
using namespace std;

bool compare(int a,int b){
    return a<=b;
}

int main(){
    int arr[]={1,2,5,10,20,50,100,200,500,2000};
    int key=120;
    int n=sizeof(arr)/sizeof(int);

    int lb=lower_bound(arr,arr n,key,compare)-arr;
    int x=arr[lb];
    cout<<x<<endl;
    

    return 0;
}

1. lower_bound возвращает итератор, указывающий на первый элемент, который не сравнивается ниже искомого значения. 100 <= 120 , !(200 <= 120) , он возвращает указатель на 200 . Почему вывод должен быть 100?

2. Вы не изменили условие, но ваша функция сравнения нарушена — она завершится ошибкой при поиске точного соответствия.

Ответ №1:

в то время как, создав свою собственную функцию сравнения, я изменил условия

Это не то, что вы compare делаете. Вы только что изменили сравнение, но таким образом, что по-прежнему 200 является первым элементом, для которого compare возвращается false .

Если вы хотите получить 100 , вы можете использовать std::prev , чтобы получить предыдущий элемент, на который указывает lower_bound :

 auto it = std::prev(lower_bound(std::begin(arr),std::end(arr),key), 1);

и теперь *it будет 100 .

Если вам нужен индекс этого элемента, вы можете использовать std::distance так:

 int index = std::distance(std::begin(arr), it);

Вот демонстрация.

Обратите внимание, что вы должны учитывать тот факт, что lower_bound может возвращать итератор в начало диапазона, и в этом случае вы не можете этого сделать std::prev .

1. Кроме того, хотя это не влияет на функциональность кода, поскольку lower_bound возвращает итератор, вам не нужно проходить арифметику указателей, а затем обращаться к массиву. Вы можете просто разыменовать возвращаемое значение или std::prev возвращаемое значение или что у вас есть, если только вам не нужен индекс массива специально. (Он не используется в примере кода аскера, но может иметь отношение к их полному применению.)

2. @NathanPierson Хорошая мысль. Я выделил итератор и индекс, поэтому OP может использовать то, что подходит.