Предположим, у меня есть набор непересекающихся действительных интервалов, например, {[0,1), [1, 5], [7.5, 9.2]}. Я хочу сохранить эту информацию в структуре данных, которая поддерживает следующие операции в постоянном времени:
find(x): с учетом числа с плавающей запятой x, это должно вернуть индекс интервала, содержащего x (или -1, если такой интервал не существует). Например find(0.5) -> 0, find(8.1) -> 2, find(6) -> -1.
Существует ли такая структура данных? И если да, то есть ли у него имя?
Лучшее, что я могу придумать, это отсортировать интервалы и реализовать find с помощью бинарного поиска, который принимает O (log k) для k интервалов.