Изменения

* 1) Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-ый каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, очевидно, в некоторых случаях уменьшит время поиска. <br>

* 2) Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-ый каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex>

Введем определения:

{{Определение

<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>

<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке.

=== Ответ на запрос ===

В первом каталоге ответ на запрос найдем с помощью бинарного поиска по <tex> C_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый ''модифицированный каталог'' мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в ''подставную вершину'', а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь <tex> cell </tex> {{---}} ''неподставная вершина'', то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранее и перешли мы вниз по ней, но это не случилось. Обновив cell максимальным из подходящих значений нужно проверить, является ли она ''подставным элементом'', если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.