Какой самый быстрый алгоритм поиска в массиве непересекающихся отрезков, поиск отрезка внутри которого лежит точка?

Question

[SergeySerge11]

У меня есть решение бинарного поиска. Оно O(ln(n) ), а есть ли решение для O(1) за одну операцию, из доп условия?
Условие.
1. Весь отрезок заполнен отрезками, без свободных мест.( и явл. константной).
2. Есть массив, элементы которого явл. Х0 отрезков. к примеру {0,1,1,2,3,5,8,13,21,34} или {1,2,4,8,16,32,}
3. Сами элементы массива. Уже сортированы, и явл. отображением некоторой функции по возрастанию Длин f(i) = x0i
К примеру из примера 2 . ф-цией f(i)=2^i , но может быть и сложнее, примерно на такое 2^(i/4).
O(1) из задачи может вытекать к примеру для любой линейной последовательности (0,10,20,30,40) тут просто поделить на 10, взять целую часть. index= value/10; А для не линейных отрезков возможно ли придумать запрос.
На вход поступает число, на выход индекс где arr[index]<= var
Да также для длинны пространства для разбития к примеру 1024, можно сделать

switch(n_1024){
case 0:
casse 1:
///....
case 1024:
}

Comments

[Lynn «Кофеман»]

Я так и не понял что за массивы в п. 2

[Akina]

А для не линейных отрезков возможно ли придумать запрос.

Можно. Всего-то и делов, что найти функцию, которая преобразует нелинейный массив начал отрезков в линейный...

[Wataru]

Т.е. даны начала отрезков и известно, что их длины не убывают? Насколько большие числа?

[Rsa97]

switch, в общем случае, преобразуется в последовательность if-ов.

if (n_1024 != 0) goto sw_1
  ...
  goto sw_end
sw_1: if (n_1024 != 1) goto sw_2
  ...
  goto sw_end
...
sw_1023: if (n_1024 != 1024) goto sw_end
  ...
sw_end:

Так что его использование эквивалентно линейному поиску в массиве.

[res2001]

Если массивы не нужны для чего-то еще, то можно использовать вместо них хэш таблицы. Там поиск за O(1).

[Yagher]

Rsa97,

Так что его использование эквивалентно линейному поиску в массиве.

Мне казалось, что это будет поиск по таблице.

Answer 1

[Wataru]

Если нет простой формулы, как в линейном случае (например, логарифм или корень числа), то за О(1) можно только если числа не очень большие: надо предподсчитать ответы для всех возможных индексов.

Если запросов много (больше чем отрезков) и они уже сортированные, то можно обработать их все сразу пачкой, пройдясь один раз по массиву отрезков. Это будет быстрее чем за логарифм обрабатывать каждый запрос отдельно. Но это очень частный случай. Сортировать запросы будет медленнее бинпоиска, если они уже не даны по порядку.

Если запрос только один, то можно не париться, ибо время на загрузку массива с отрезками вы уже потратили и вся программа уже точно O(n) как минимум.

Answer 2

[mayton2019]

Ваше решение O(ln(n)) - это очень хорошее решение. Пускай оно и будет.

Для других оптимизаций нужно строить дополнительные структуры данных. Например хеш таблица которая режет пространство отрезков на линейную последовательность равных кусков и для каждого куска хранит просто список ваших отрезков. Будет некоторая избыточность зато у вас есть почти O(1) и есть механика плавного регулятора. Тоесть вы можете балансировать сколько вам отдать памяти под хеш таблицу и сделать результат более точным. Или наоборот сэкономить но сделать чуть-чуть O(n). Мне почему-то фантазия подсказывает какие-то золотые сечения и теорему Котельникова ... ну вобщем у вас есть широкое пространство для творчества.

Comments

[Wataru]

Можно поподробнее расписать? Какой-нибудь пример вроде, как отрезки длинами 1,3,4,7 будут порезаны хеш таблицей на "линейную последовательность равных кусков" и как это потом будет работать за O(1)?

[mayton2019]

Wataru, тут чего-то не хватает. 1,3,4,7 - это только x1 координаты. А где x2?

[Wataru]

mayton2019, Это длины же. Пусть будет Отрезок 1..15 распилен на 4 отрезка вот так: [1,1], [2,4], [5,8], [9,15]

[mayton2019]

Ну вот. У нас дискретный шаг в единичку. Создавайте хеш-табличку в 15 ключей. И каждому ключу сопоставляейте ссылку на отрезок. Мемоизация. Так любую детерминистик-функцию можно отобразить. Ну если будет наложение отрезков - тогда ничего не поделать. Список выдадим.

[Wataru]

mayton2019, Так тут не хеш-таблица нужна, а тупо массив. Ведь по условию отрезки не пересекаются и заполняют весь интервал 1..N

[mayton2019]

Wataru, ну Okay. Это частный случай. И вобщем-то его обсуждать то не интересно.

P.S. Когда я разбирался с базой IP-blocks то меня заинтересовал способ поиска айпи адреса принадлежащего блоку. Вобщем там работало префиксное дерево. И помимо скорости принятия решений оно еще и обеспечивало физическую оптимизацию объема. Примерно на 300 мб айпи блоков выходило около 30 мб сжатого префиксного дерева.