stl — Поиск диапазона [x, y] в отсортированном в C ++ векторе [с использованием lower_bound () и upper_bound ()]
У меня есть массив отсортированных векторов,
вектор< int> b [1000009];
Теперь я должен искать диапазон между x и y включительно в строке b [factor].
‘factor’, ‘x’ и ‘y’ являются целыми числами.
Я использовал следующий подход:
int lb,ub;
if(b[factor][0]>=x){lb=0;}
else
{
lb=upper_bound(b[factor].begin(),b[factor].end(),x)-b[factor].begin();
while(b[factor][lb-1]>=x)lb--;
}
if(b[factor][sz2-1]<=y)
{
ub=sz2-1;
}
else {
ub=lower_bound(b[factor].begin(),b[factor].end(),y)-b[factor].begin();
while(b[factor][ub]>y)ub--;
}
Но этот подход не дает правильных ответов все время. Кроме того, я хотел бы использовать некоторые функции сравнения для достижения того же. Это мой первый раз с нижняя граница() а также верхняя граница(). Поэтому, пожалуйста, скажите мне, как реализовать функцию компаратора здесь.
Решение
std::lower_bound возвращает позицию первого элемента, значение которого больше или равно аргументу. std::upper_bound возвращает позицию первого элемента, который больше аргумента. Вы можете использовать их для перебора диапазона значений между x и y следующим образом:
auto vb = b[factor].begin();
auto ve = b[factor].end();
auto lb = lower_bound(vb,ve,x);
auto ub = upper_bound(vb,ve,y);
for (auto i=lb; i!=ub; ++i) {
// Do something with *i
}
Давайте возьмем этот пример. Скажем, наш вектор содержит эти значения:
1 3 4 7 9
И скажем, х = 3 и у = 7. std::lower_bound(vb,ve,x) вернет позицию первого значения, которое больше или равно 3. Поскольку существует значение, равное 3, его позиция — это то, что мы получим для нижней границы.
std::upper_bound(vb,be,y) вернет позицию первого значения, которое больше 7. Это будет позиция 9 в этом случае.
Таким образом, наш цикл идет от позиции 3 до, но не включая, позиции 9, которая является именно тем диапазоном значений, который мы хотим.
А что если x = 5 и y = 6. Там не будет никаких значений в этом диапазоне. Что бы это сделать?
Первое значение, которое больше или равно 5, равно 7. Первое значение, которое больше 6, также равно 7. Так lb а также ub будет такая же позиция! Наш цикл завершился бы немедленно, и это именно то, что мы хотим, так как в нашем диапазоне нет элементов.
Другие решения
Других решений пока нет …