Карточка Junior Бинарный поиск обновлено
Шаблон lower bound
Вопрос
Как выглядит надёжный шаблон «первый индекс, где условие истинно»?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
l = 0, r = n; пока l < r: mid = (l + r) 1; если условие(mid) истинно, r = mid, иначе l = mid + 1. Возврат l (может быть n, если такого нет).
Ответ
l = 0, r = n; пока l < r: mid = (l + r) >> 1; если условие(mid) истинно, r = mid, иначе l = mid + 1. Возврат l (может быть n, если такого нет). Полуинтервал [l, r) не даёт зацикливаний.
Разбор
l = 0, r = n; пока l < r: mid = (l + r) >> 1; если условие(mid) истинно, r = mid, иначе l = mid + 1. Возврат l (может быть n, если такого нет). Полуинтервал [l, r) не даёт зацикливаний.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.