Изменения
Добавлен первый способ решения
'''Техника частичного каскадирования''' (англ. ''fractional cascading technique'') {{---}} это способ организации структуры данных, который предназначен для быстрого итеративного поиска в <tex> k </tex> каталогах.
{{Задача
|definition = Дано <tex> k </tex> каталогов <tex> C_i </tex>, каталог <tex>i</tex> представляет собой упорядоченный массив размера <tex> n_i </tex>. Поступают запросы, которые представляют собой один элемент <tex> x </tex>. Требуется для каждого запроса определить в каждом каталоге элемент меньше либо равный <tex> x </tex>.
}}
== Различные подходы к решению ==
Пусть <tex> n = \sum\limits_{i = 1}^k n_i </tex>.
<br>
1) Пусть пришел запрос <tex> x </tex>. Пробежимся по всем каталогам. Пусть мы находимся в <tex> i</tex>-ом каталоге, тогда мы можем ответить на запрос для данного каталога за <tex> O(\log n_i) </tex> используя бинарный поиск. Так как каталогов <tex> k </tex> штук, то в итоге мы обработаем запрос за <tex> O(k \log n) </tex>. Для хранения всех каталогов понадобится <tex> \Theta(n) </tex> памяти.
<br>
