Изменения

Перейти к: навигация, поиск

Упорядоченное множество

881 байт добавлено, 00:46, 1 июля 2015
successor
=== '''successor''' ===
Выполняется аналогично В операции используется [[Целочисленный двоичный поиск|левосторонний бинарный поиск]], который вернет такое <tex>\mathrm {search(seti</tex>, что <tex> s.elements[i - 1]<elem)}\leqslant s.elements[i] </tex>.
<code>
'''T''' successor(Set<T> s, T elem):
'''int''' i = binSearch(s.elements, elem) '''if''' elem > s.elements[i] == elem '''and''' i < s.n - 1 ] <font color=green>// ЭлементЕсли элемент больше максимального, следующий за последним, не существует.</font color=green> '''return''' s''null'' <font color=green>// возвращаем ''null''.elements[i + 1]</font color=green>
'''else'''
'''if''' elem < s.elements[0] <font color=green>// Если элемент меньше минимального,</font color=green> i = 0 <font color=green>// возвращаем минимальный элемент.</font color=green> '''else''' i = binSearch(s.elements, elem) <font color=green>// Иначе ищем элемент, больший либо равный ''elem''.</font color=green> '''if''' s.elements[i] == elem '''return''' s.elements[i + 1] ' ''nullelse''' '''return'''s.elements[i]
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.
Анонимный участник

Навигация