1632
правки
Изменения
м
=== '''predecessor''' ===
Выполняется аналогично операции <tex>\mathrm {search(set, elem)}</tex>.
<code>
'''T''' predecessor(Set<T> s, T elem):
'''int''' i = binSearch(s.elements, elem)
'''if''' s.elements[i] == elem '''and''' i > 0 <font color=green>// Элемент, предшествующий первому, не существует.</font color=green>
'''return''' s.elements[i - 1]
'''else'''
'''return''' ''null''
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.
Выполняется аналогично В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <tex>i</tex>, что <tex>s.elements[i - 1]\mathrm {search(set, leqslant elem)}< s.elements[i] </tex>.
* Если задан массив с повторяющимися элементами, то в операциях <tex>\mathrm {predecessor(set, elem)}</tex> и <tex>\mathrm {successor(set, elem)}</tex> следует использовать левосторонний и правосторонний [[Целочисленный двоичный поиск|бинарный поиск]] соответственно.
rollbackEdits.php mass rollback
'''bool''' search(Set<T> s, T elem):
'''int''' i = binSearch(s.elements, elem)
'''ifreturn''' s.elements[i] == elem <font color=green>// Сравниваем найденное значение с искомым...</font color=green> '''return''' ''true'' '''else''' '''return''' ''false''
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>.
</code>
Время выполнения {{---}} <tex>O(1)</tex>.
=== '''successor''' ===
<code>
'''T''' successor(Set<T> s, T elem):
'''intif''' i = binSearch(elem > s.elements[s.n - 1] <font color=green>// Если элемент больше максимального, elem)</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green> '''else if''' elem < s.elements[i0] == elem '''andreturn''' i < min(s.n - 1 ) <font color=green>// Элемент, следующий за последнимЕсли элемент меньше минимального, не существуетвозвращаем минимальный элемент.</font color=green> '''returnint''' i = binSearch(s.elements[i + 1] , elem) <font color=green>// Иначе ищем элемент, больший '''else'elem''.</font color=green> '''return''' ''null''s.elements[i]
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
== Замечания ==
* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
== Примеры ==
