390
правок
Изменения
→Поиск элемента
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]]
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
# Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже были на первом уровне <tex>-</tex> прекратить поиск.и вернуть ссылку на текущую вершину
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на хвост списка на первом уровне.
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
