Изменения
→successor
== Наивная реализация на массиве ==
Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного ]] массива <tex>elements[0..n-1]</tex>.
Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.
'''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):
'''if''' s.elements[0] <= elem '''&&''' > s.elements[s.n- 1] > elem <font color=green>// Если элемент ''elem'' существует и не равен максимальномубольше максимального,</font color=green> '''intreturn''' ''null'' i = binSearch(s.elements, elem) <font color=green>// то ищем индекс элемента возвращаем ''elemnull''.</font color=green> '''returnelse if''' elem < s.elements[i + 10] '''return''' min(s) <font color=green>// и выводим следующий за ним Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''elseint''' i = binSearch(s.elements, elem) <font color=green>// В противном случаеИначе ищем элемент, больший ''elem''.</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''s.</font color=green>elements[i]
</code>
Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.
== Замечания ==
* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
== Примеры ==