Как найти первый меньший элемент, чем целое число X в векторе? (C ++)
Если у меня есть следующий вектор {10 10 10 20 20 20 30 30}
и я хочу, чтобы функция возвращала позицию целого числа = X или непосредственно меньший элемент после X, как, например, если я ищу 11, я хочу, чтобы функция возвращала 2, так как 2-й элемент (10) является первым меньшим Элемент, чем 11 в векторе.
Я пытался использовать lower_bound, но это не работает.
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
vector<int>::iterator low,up;
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
low=lower_bound (v.begin(), v.end(), 11); //
up= upper_bound (v.begin(), v.end(), 11); //
cout << "lower_bound at position " << int(low- v.begin()) << endl;
cout << "upper_bound at position " << int(up - v.begin()) << endl;
return 0;
этот код выводит:
lower_bound at position 3
upper_bound at position 3
Решение
Cppreference сообщает мне, что std::lower_bound
Возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который не менее стоимости
а также std::upper_bound
Возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который больше чем значение
В этом случае дан вектор, содержащий 10 10 10 20 20 20 30 30 Я ожидаю, что обе функции будут указывать на первую 20, который находится в позиции 3 в векторе и действительно является результатом, который вы получили оба раза. Если бы вы вместо этого попросили 20, std::lower_bound вернет итератор, указывающий на первый 20 в векторе (позиция 3) … первое число не менее 20 и тот же результат, который вы получите при запросе 11, В этом случае, хотя, std::upper_bound вернет итератор, указывающий на первый 30 (позиция 6), которая является первым значением больше 20.
Просто переместите итератор на один, чтобы получить последнее значение меньше целевого числа, std::prev это один из способов сделать это.
Другие решения
Итак, upper_bound возвращает первый элемент, который больше, чем тестовый элемент, так что предыдущий (если он существует) будет тем, который вам нужен?
Вы могли бы сделать это … может быть, лучше вернуть итератор, если вектор пуст …
auto find_next_smaller(vector<int> vec, const int x) {
std::sort(vec.begin(), vec.end());
auto it = std::lower_bound(vec.begin(), vec.end(), x);
if (it == vec.end()) {
it = (vec.rbegin()+1).base();
}
else if (it != vec.begin() && *it > x) {
--it;
}
return it;
}