lower_bound () дает неверный результат

Question

Я написал код, где мне нужно найти lower_bound из квадратной числовой последовательности.Но нижняя граница дает мне результат для upper_bound ..

Вот мой код и ссылка на компилятор: http://cpp.sh/3cppb

// Example program
#include <iostream>
#include <string>
#include <algorithm>

int main()
{
   std::vector<int> v{ 1, 4, 9, 16, 25 }; // all the square numbers

   int x = std::lower_bound(v.begin(), v.end(), 5) - v.begin() ;

   std:: cout<<"Postion "<<x<< "  value  "<<v[x] <<std::endl; //getting output for upperbound

}

Вывод:

Postion 2  value  9

Ожидаемый результат

Postion 1  value  4

Answer 1

std::lower_bound работает правильно.Функция возвращает первый элемент, который не меньше предоставленного значения.Поскольку 9 - это первое значение, которое не меньше 5, вы получите этот элемент.

std::upper_bound в этом случае вернет тот же элемент, так как он возвращает первый элемент больше указанного значения.Здесь вы увидите разницу, например

std::vector data = {4,4,4};
auto low = std::lower_bound(data.begin(), data.end(), 4);
auto high = std::upper_bound(data.begin(), data.end(), 4);

. В этом случае low будет begin(), так как 4 не меньше 4, а high будет end(), поскольку элемент отсутствуетбольше 4 в векторе.

Answer 2

Цитата из стандарта, [lower.bound]:

template<class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

Возвращает: самый дальний итератор i в диапазоне [first,last] такой, что дляДля каждого итератора j в диапазоне [first,i) выполняются следующие соответствующие условия: *j < value.

Answer 3

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

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

Поскольку 9 - это первое значение, которое больше или равно5 (конечно, это больше), результат совершенно верный.

Если бы вы попытались найти элемент, который уже находится в v, например 9, вы бы получили другие результаты.для std::lower_bound и std::upper_bound:

std::distance(begin(v), std::lower_bound(begin(v), end(v), 9)); // 2
std::distance(begin(v), std::upper_bound(begin(v), end(v), 9)); // 3