Есть ли алгоритм поиска элемента в skip-list со сложностью O (log (k))

Question

Я получил довольно простую домашнюю задачу в своем университете, но все еще не могу ее решить: для заданного значения X , которое впервые появляется в списке пропусков, это индекс k ,создайте алгоритм, который находит X в индексе k со сложностью O (log (k)) .Ранее я видел, что люди спрашивают об этом, но ни на один вопрос не ответили четко и понятно.Я просто не могу придумать, как это сделать.Существует очень понятное решение для поиска элемента со временем O (log (k)) в простом массиве, где применяется экспоненциальный поиск.Буду очень признателен, если кто-нибудь опишет сам алгоритм и идею, которую он использует.Заранее спасибо.

Answer 1

Сначала пройдите указатели переадресации, чтобы найти самый высокий, который вы можете пройти без прохождения X .Это займет O (log k) .

Затем продолжите поиск как обычно, начиная с этого указателя вместо самого высокого.Для этого также требуется O (log k) .

Большинство структур данных, которые предлагают поиск O (log N) , также поддерживают оптимизированный поиск соседних элементов, таких как этот, впо крайней мере, когда вы начинаете с любого конца.Это называется «поиск по пальцу»: https://en.wikipedia.org/wiki/Finger_search

Answer 2

Согласно http://bigocheatsheet.com/ поиск списка пропусков - O (log (n)).

Еще один полезный ресурс, кроме вики (https://www.geeksforgeeks.org/skip-list-set-3-searching-deletion/) псевдокод:

Search(list, searchKey)
x := list -> header
-- loop invariant: x -> key  level downto 0 do
    while x -> forward[i] -> key  forward[i]
x := x -> forward[0]
if x -> key = searchKey then return x -> value
else return failure