Алгоритмы trainee
Как работает бинарный поиск?
Ответ
Только для отсортированного массива. Берём середину, сравниваем с искомым. Если меньше — ищем в левой половине, больше — в правой. Каждая итерация — ÷2. Сложность O(log n).
Разбор: Бинарный поиск требует уже отсортированного массива, на каждом шаге сравнивает искомое с серединой и переходит в нужную половину, отбрасывая вторую, что даёт O(log n). Сам он не сортирует данные (иначе это O(n log n)), а в третьем варианте направления перепутаны: если середина меньше искомого, идти надо вправо, а не влево.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.