Почему поиск элемента по значению в std::set имеет сложность O(log n)?

set::find имеет логарифмическую сложность благодаря упорядоченной структуре поиска; обычно это сбалансированное дерево. Его высота растёт как log n, поэтому проверяется лишь один путь.

На каждом шаге сравнение направляет поиск в подходящее поддерево. Стандарт задаёт требование к сложности, но не обязывает использовать именно красно-чёрное дерево.

Важно вызывать s.find(key): универсальный std::find(s.begin(), s.end(), key) последовательно обходит элементы и имеет линейную сложность. Если сравнение ключей само по себе дорогое, это также влияет на фактическое время.