Выбор ответа Middle Бинарный поиск обновлено
Поиск в повёрнутом массиве
Вопрос
Отсортированный массив без дубликатов повернули: [4, 5, 6, 7, 0, 1, 2]. Как найти элемент за O(log n)?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Бинпоиск: одна из половин всегда отсортирована, проверяем её. Если arr[l] <= arr[mid], левая половина отсортирована, иначе правая.
Варианты ответа
- Линейный поиск: после поворота бинпоиск тут не работает
- Бинпоиск: одна из половин всегда отсортирована, проверяем еёправильный ответ
- Сначала отсортировать массив, затем запустить обычный бинпоиск
- Бинпоиск по обычному правилу сравнения, поворот не мешает
Разбор
Если arr[l] <= arr[mid], левая половина отсортирована, иначе правая. Проверяем, попадает ли x в диапазон отсортированной половины, и отбрасываем лишнее. O(log n).
- Линейный поиск O(n), задача решается быстрее.
- Сортировка O(n log n).
- Обычное правило ошибётся: в
[4,5,6,7,0,1,2]приmid = 3и x = 1 сравнение7 > 1уведёт влево, а x справа.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.