Карточка Junior Бинарный поиск спрашивают часто обновлено
Сложность бинпоиска
Вопрос
Какая сложность у бинарного поиска и почему?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
O(log n): каждый шаг отбрасывает половину диапазона, поэтому шагов около log₂ n. Для миллиона элементов это около 20 сравнений.
Ответ
O(log n): каждый шаг отбрасывает половину диапазона, поэтому шагов около log₂ n. Для миллиона элементов это около 20 сравнений. Память O(1) в итеративной версии.
Разбор
O(log n): каждый шаг отбрасывает половину диапазона, поэтому шагов около log₂ n. Для миллиона элементов это около 20 сравнений. Память O(1) в итеративной версии.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.