Самый быстрый способ найти ближайшие границы из ряда значений

Question

Допустим, я отсортировал предварительно вычисленные числа с плавающей точкой:

1, 3, 10, 29

Допустим, мой "вход" - 7.3. Я хочу, чтобы моя программа возвращала 3 и 10, поскольку они являются числами в моем массиве до и после 7.3.

Какой самый быстрый способ сделать это? Я предполагаю, что вы можете сделать это за log(n) время, используя бинарный поиск, но возможно ли сделать это за постоянное время?

Answer 1

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

Answer 2

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

Функция C ++ для бинарного поиска: lower_bound. (Есть и другие, но вы хотите lower_bound.)