Приветствую )
Имеется большой список со значениями (пускай будет vector, хотя использую deque) - как бы найти первый ближайший элемент, который меньше или равен значению???
На основании (а так же из-за наличия только 11/14) запили реплику
ssize_t cnt = q.size() - 1;
size_t m, l = 0, i = 0;
while (cnt > 0)
{
i = l;
m = cnt / 2;
i += m;
if (q.at(i) < val)
{
l = ++i;
cnt -= m + 1
}
else
cnt = m;
}
все бы хорошо, НО находится всегда первый после val, std::upper_bound тоже пробовал реализовать, но всегда получаю последний элемент, поскольку почти никогда не имею значения val в массиве.
З.Ы. сдвинуться на назад можно на элемент, но хочется понять почему при бинарном поиске получается индекс справа, а не слева!?
или например еще один из вариантов бинарного поиска
size_t m, l = 0, r = q.size() - 1;
while (l < r)
{
m = (l + r) / 2;
if (q.at(m) < val)
l = m + 1;
else if (q.at(m) > val)
r = m - 1;
else
break;
}
Но при этом получаю то слева, то справа индекс очевидно в зависимости от результата целочисленного деления.
З.Ы. и тут результат конечно можно перепроверить после цикла, но как бы гарантированно сразу получить элемент слева от числа???
