Lower_bound не работает с последним элементом вектора с 3 элементами

vector<int> vec = {2,4,3};
vector<int>::iterator it;
it=lower_bound(vec.begin(),vec.end(),3);
cout<<*it;

Это возвращает результат 4 не 3, а

vector<int> vec = {2,3,4};
vector<int>::iterator it;
it=lower_bound(vec.begin(),vec.end(),3);
cout<<*it;

Но это возвращает правильный результат 3. Пожалуйста, помогите мне понять, почему это терпит неудачу в угловом случае.

Всего 2 ответа


Согласно cppreference и его документации std::lower_bound :

Возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который не меньше (то есть больше или равен) значению, или last, если такой элемент не найден.

Итак, std::lower_bound возвращает первый элемент, который больше или равен значению (здесь 3).

Для {2, 4, 3} первый элемент, больший или равный 3, равен 4, а для {2, 3, 4,} - 3.

PS По cppreference еще раз:

Диапазон [first, last) должен быть разделен по отношению к элементу выражения <value или comp (element, value) , т. Е. Все элементы, для которых выражение является истинным, должны предшествовать всем элементам, для которых выражение является ложным. Полностью отсортированный диапазон соответствует этому критерию.

Оба ваших вектора правильно разделены с условием (элемент <значение)


Короче говоря, вектор {2,4,3} не соответствует требованиям lower_bound .

https://en.cppreference.com/w/cpp/algorithm/lower_bound говорит:

Диапазон [first, last) должен быть разделен по отношению к элементу выражения <value или comp (element, value), т. Е. Все элементы, для которых выражение является истинным, должны предшествовать всем элементам, для которых выражение является ложным. Полностью отсортированный диапазон соответствует этому критерию.

Если ваш вектор не отсортирован, используйте std::find .


Есть идеи?

10000