Какова сложность бинарного поиска?

Сложность бинарного поиска в худшем и среднем случае равна O(log n). В лучшем случае — O(1).