Выбор ответа Junior Бинарный поиск обновлено
Первое вхождение
Вопрос
В отсортированном массиве с дубликатами нужно найти первый индекс числа x. Что делать, когда arr[mid] === x?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Запомнить mid и продолжить слева, сдвигая r = mid - 1. Найденное вхождение может быть не первым.
Варианты ответа
- Запомнить
midи продолжить слева, сдвигаяr = mid - 1правильный ответ - Сразу вернуть
mid: найденный индекс и есть первый - Запомнить
midи продолжить справа:l = mid + 1 - Идти линейно влево от
mid, пока значение равно x
Разбор
Найденное вхождение может быть не первым. Сохраняем кандидата и сужаем поиск влево. Итог O(log n).
- Возврат
midдаст любое вхождение. - Поиск справа найдёт последнее.
- Линейный проход влево при большом числе дубликатов O(n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.