Выбор ответа Junior Бинарный поиск спрашивают часто обновлено
Когда применим бинпоиск
Вопрос
Какое условие обязательно для бинарного поиска?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Монотонность условия: ложно до точки, истинно после. Бинпоиск отбрасывает половину, опираясь на монотонность предиката.
Варианты ответа
- Массив без дубликатов, иначе поиск зациклится
- Монотонность условия: ложно до точки, истинно послеправильный ответ
- Длина массива должна быть степенью двойки
- Массив целых чисел, чтобы
midделился без остатка
Разбор
Бинпоиск отбрасывает половину, опираясь на монотонность предиката. Отсортированный массив частный случай. Ещё пример: бинпоиск по ответу.
- Дубликаты допустимы, нужен только правильный вариант поиска.
- Длина может быть любой.
- Тип элементов не важен, важно сравнение.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.