Изменения
→successor
== Наивная реализация на массиве ==
Упорядоченное множество <tex>s</tex>, содержащее <tex>n</tex> элементов, можно реализовать с помощью [[Сортировки | отсортированного ]] массива <tex>elements[0..n-1]</tex>.
Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.
=== '''search''' ===
Для нахождения результата используем [[Целочисленный двоичный поиск|бинарный поиск]].
<code>
'''Tbool''' search(Set<T> s, T elem): '''if''' s.elements[0] <= elem '''&&''' s.elements[s.n] >= elem <font color=green>// Если элемент ''elem'' существует, то</font color=green> '''int''' i = binSearch(s.elements, elem) <font color=green>// ищем индекс элемента ''elem''</font color=green> '''return''' s.elements[i] == elem <font color=green>// и выводим его Сравниваем найденное значениес искомым..</font color=green> '''else''' <font color=green>// В противном случае</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green>
</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> выполняется аналогичным образом.
== Замечания ==
* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].
== Примеры ==
* множество натуральных чисел <tex> \mathbb N </tex>,
* множество целых чисел <tex> \mathbb Z </tex>,
* строки, отсортированные в лексикографическом порядке. == См. также ==* [[Вещественный двоичный поисклексикографический порядок|Бинарный поисклексикографическом порядке]].
== Источники информации ==
