Лучший способ сравнить элементы в векторе и вернуть объект

Question

У меня есть случай, когда числа монотонно растут в векторе целых чисел

vec[0] = 2
vec[1] = 5
vec[2] = 8
vec[3] = 10
..

Если мне передают номер 6, я хочу вернуть vec [1], так как он лежит между vec [1] и vec [2], аналогично, если проходы 9 должны будут возвращать vec [2]. Мой опыт работы с STL ограничен, поэтому я хотел проверить, можем ли мы решить эту проблему с помощью STL, или вам придется перебирать каждый из них, сохраняя предыдущее значение, и когда вы наберете число, превышающее переданное число, вы вернете

Answer 1

STL имеет четыре повторно используемых алгоритма двоичного поиска в заголовке <algorithm>: lower_bound, upper_bound, equal_range и binary_search.

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

Answer 2

Вы можете использовать бинарный поиск.

Answer 3

В заголовке <algorithm> есть функция binary_search(). К сожалению, эта функция возвращает только логическое значение. Вы можете написать свой собственный бинарный поиск по отсортированному вектору, что будет быстрее для больших списков, чем линейный поиск, на который намекают в исходном сообщении. (Прошу прощения, если я неправильно прочитал сообщение).