Эффективна ли функция find () для множеств?

Question

Насколько мне известно, бинарный поиск - это наиболее эффективный способ определить, существует ли определенный элемент x в отсортированном массиве.Таким образом, мне было интересно, если это хорошая идея, чтобы использовать функции find () или count () для выполнения этого процесса поиска элемента, или более разумно использовать отсортированный массив, а не набор иприменить метод двоичного поиска.

Answer 1

set::find() достаточно эффективен, O (log n).

Если вам не нужен доступ к элементам по порядку, вам следует рассмотреть возможность использования unordered_set.unordered_set::find() в среднем равно O (1).

Answer 2

Да, это эффективно.

Набор содержит уникальные и отсортированные элементы.Поэтому find () использует бинарный поиск и имеет сложность O (logN) в наборе из N элементов.Вставка тоже логарифмическая, чтобы сохранить ее сортировку и уникальность.