Двоичный поиск с подсказкой

У меня есть простой std::vector содержащий некоторые числа, которые сортируются (в порядке возрастания). Я хочу найти элемент, до сих пор использую:

return std::lower_bound(vec.begin(), vec.end(), needle);

Где needle - элемент, который я ищу. Однако мой вектор имеет тенденцию быть довольно длинным (миллионы элементов), но большую часть времени контент относительно предсказуем в некотором смысле, что если первый элемент равен нулю, а последний элемент N, то элементы между ними имеют значение, близкое к (N * index) / vec.size() и, следовательно, предсказуемо.

Есть ли модификация нижней границы, которая будет принимать подсказку (подобно тому, как это делается std::map::emplace_hint()), например:

assert(!vec.empty());
std::vector<int>::iterator hint = vec.begin() + std::min(vec.size() - 1,
    (needle * vec.size()) / vec.back());
if(*hint > needle)
    return std::lower_bound(vec.begin(), hint, needle);
else
    return std::lower_bound(hint, vec.end(), needle);

Это будет работать, но lower_bound игнорирует, что он близок к решению и, скорее всего, начнет разделять интервал на половинки (смотря, где мы знаем, что игла, скорее всего, нет), делая излишне много шагов. Я знаю, что существует алгоритм, который начинается с шага 1, который он удваивает, пока он не перекроет иглу, а затем выполняет бинарный поиск в заданном интервале.

Я забыл, что такое имя алгоритма. Это реализовано в STL?

Ответы

Ответ 1

Я думаю, что алгоритм, который вы ищете, называется интерполяционным поиском, который является вариацией бинарного поиска, который вместо того, чтобы смотреть на середину массива, линейно интерполирует между конечными точками массива, чтобы угадать, где должен быть ключ. На данных, которые структурированы так, как вы есть, ожидаемая продолжительность выполнения - O (log log n), экспоненциально быстрее, чем стандартный двоичный поиск.

Стандартная реализация этого алгоритма в С++ отсутствует, но (как совершенно бесстыдный плагин) мне пришлось закодировать этот код на С++. Моя реализация доступна онлайн, если вам интересно, как это работает.

Надеюсь, это поможет!