1632
правки
Изменения
м
=== '''predecessor''' ===
Выполняется аналогично операции <tex>\mathrm {search(set, elem)}</tex>.
<code>
'''T''' predecessor(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 - 1] <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>.
Выполняется аналогично В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], который вернет такое <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
== Наивная реализация на массиве ==
Упорядоченное множество <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 Z </tex>,
* строки, отсортированные в [[лексикографический порядок|лексикографическом порядке]].
== Источники информации ==
