ENRU
ВойтиЗарегистрироваться бесплатно
Все темы
30

Найти точное место, где «нет» превращается в «да»

Tier 1Бесплатно

Где применяется

1. Задача

В приложении появился баг. Версия 40 работает, версия 90 сломана. Где-то между ними одно изменение (коммит) всё сломало. С этого коммита каждая сборка падает. Тебе нужна первая плохая версия.

Проверка одной версии идёт медленно: ты собираешь её и запускаешь все тесты. Между 40 и 90 лежат 50 версий. Проверить все подряд значит 50 прогонов тестов, это часы ожидания.

Но у результатов есть порядок. Сначала идут успешные сборки, потом упавшие, и так до самого конца. Если сборка сломалась, она остаётся сломанной во всех следующих версиях.

Благодаря этому порядку место перехода находится примерно за 6 проверок вместо 50. Ты ищешь границу тем же делением пополам, что в прошлом уроке. Разница одна: там искали конкретное значение, а здесь ищешь место, где «работает» сменяется на «сломано».

2. Простыми словами

Возьми 6 позиций с номерами от 0 до 5. Проверка на позициях 0, 1 и 2 отвечает «нет», на позициях 3, 4 и 5 отвечает «да». Ты этого заранее не знаешь и хочешь найти первое «да».

Проверяешь позицию посередине, номер 3. Ответ «да». Значит, первое «да» стоит на позиции 3 или раньше, и позиции 4 и 5 можно больше не проверять. Проверяешь позицию 1: «нет». Значит, всё до неё тоже «нет», и первое «да» стоит правее. Остаётся позиция 2: «нет». Значит, первое «да» на позиции 3.

Отличие от обычного бинарного поиска видно на первом шаге. Позиция 3 ответила «да», но поиск не остановился. Ты не знал, что позиция 2 ответит «нет», поэтому продолжил смотреть левее. Тебе нужно самое первое «да», а не любое.

3. Идея

У тебя есть проверка «да/нет». Здесь это isFailing(version). Проверка монотонная: если она один раз ответила true, то на всех следующих позициях тоже ответит true. Поэтому ответы выглядят так: false, false, ..., true, true, true. Тебе нужен первый true.

Работай с диапазоном от lo до hi, где сначала lo = 0, а hi = n. Всё время держи верным одно правило. На всех позициях левее lo проверка даёт false. На позиции hi и правее она даёт true. Позиции n в списке нет, она стоит сразу за последней. Старт hi = n оставляет место для ответа «ни одного true нет».

Повторяй, пока lo < hi. Смотри на середину. Если там true, первый true стоит в середине или левее. Поэтому опусти hi до mid. Не до mid - 1: сам mid может оказаться ответом. Если там false, первый true стоит строго правее. Поэтому подними lo до mid + 1. Когда lo и hi сойдутся, это и есть первый индекс с true. Если true не было вовсе, они сойдутся на n.

Главное отличие от прошлого урока: найдя true, ты не останавливаешься. Обычный бинарный поиск возвращает ответ сразу, как только нашёл совпадение. Этот поиск запоминает место через hi и продолжает искать левее. Поэтому он находит именно первую позицию, даже когда подходящих позиций много.

F F F T T T 0 1 2 3 4 5 первый true → индекс 3

Проследим на n = 6 и проверке «индекс ≥ 3»:

  • Начало: lo = 0, hi = 6. Середина 3, там true, поэтому hi = 3.
  • Теперь lo = 0, hi = 3. Середина 1, там false, поэтому lo = 2.
  • Теперь lo = 2, hi = 3. Середина 2, там false, поэтому lo = 3.
  • Теперь lo = 3, hi = 3. Они сошлись, возвращаем 3.

4. Во что это обходится

Время: O(log n) вызовов проверки, потому что диапазон на каждом шаге уменьшается вдвое. Память: O(1), только два индекса.

Здесь число вызовов проверки важнее обычного. Один вызов может означать целую сборку или сетевой запрос на несколько секунд. 6 вызовов вместо 50 означают короткий перерыв на кофе вместо ожидания до обеда.

6. Где это встречается

git bisect ровно так сужает диапазон коммитов (изменений кода) до первого плохого. Пороги раскатки фича-флагов (переключателей, которые включают новую функцию части пользователей). Функции lower_bound и upper_bound в стандартных библиотеках. Их разность даёт число вхождений значения. Поиск первой записи лога после заданного момента времени. Таблицы тарифов и квот, где ищут первый уровень, в который попадает значение.

Как узнать

Бинарный поиск (массив) (Binary search (array))

Эти слова в условии значат этот паттерн

  • отсортированный массив
  • найти цель / первое или последнее вхождение
  • n до 1e6+ и ожидается O(log n)
  • найти границу, где условие меняется
  • поиск во вращённом, но почти отсортированном массиве (с подвохом)

Похоже, но не то

  • Линейный поиск (Linear search)

    Перебор читает каждый элемент, но порядка не требует. Бинарному поиску порядок нужен, зато он читает log n.

  • Бинарный поиск во вращённом массиве (Binary search on a rotated array)

    Поворот рвёт единый отсортированный кусок. Проверка сначала ищет отсортированную половину.

  • Бинарный поиск по ответу (Binary search on the answer)

    Там отрезок это множество возможных ответов, а не массив. Проверку вы пишете сами.

  • Двоичное дерево поиска (Binary search tree)

    Дерево делит пополам так же, но через указатели. Ещё оно допускает вставки, чего массив не умеет.

  • Два указателя (с концов) (Two pointers (opposite ends))

    Там двигаются оба конца, и проверяемая пара меняется. Здесь за шаг двигается одна граница.

n до 1e9 нормально, потому что log2 от 1e9 около 30. Время O(log n), память O(1).

На LeetCode

Задачи, где нужно первое место, в котором ответ меняется с «нет» на «да», например первая плохая версия, место вставки или первая и последняя копия значения. Держи hi на «да» и сдвигай lo за «нет».

Твоя задача (Tier 1)

Напиши функцию firstTrue(n, pred).

pred(i) это проверка «да/нет». Её можно вызвать на любой позиции i от 0 до n - 1. Сначала она какое-то время отвечает «нет», потом «да», и к «нет» уже не возвращается. Найди первую позицию, где она отвечает «да». Если «да» не будет ни разу, верни n.

  • Вход: n, число позиций (от 0 до n - 1), и pred, функция, которая получает позицию и возвращает true или false. Пример: n = 6 и проверка, которая даёт true, когда i >= 3.
  • Возвращает: наименьшую позицию, где pred даёт true, или n, если true не будет ни разу.

Шаги:

  1. Задай lo = 0 и hi = n.
  2. Пока lo < hi, возьми среднюю позицию mid. Если pred(mid) даёт true, ответ на mid или левее, поэтому задай hi = mid. Если false, ответ правее, поэтому задай lo = mid + 1.
  3. Когда lo и hi сойдутся, верни lo.

Тесты передают ответы проверки списком flags: позиция i отвечает flags[i], а n равно длине списка.

Готово, когда проходят все тесты:

  • [false, false, false, true, true, true] -> 3 (true начинается в середине)
  • [false, false, false, false, true] -> 4 (true только на последней позиции)
  • [true, true, true] -> 0 (true с самого начала)
  • [false, false, false] -> 3 (true нет ни разу, верни n, то есть 3)
  • [false, true, true, true, true] -> 1 (список [1, 2, 2, 2, 5] с проверкой nums[i] >= 2)
  • [true] -> 0 и [false] -> 1 (n = 1)
  • [] -> 0 (n = 0, позиций нет совсем)

Практика

firstTrue

firstTrue(n, pred) -> the first index where pred is true, or n

// firstTrueFlags is given: it passes a list of flags (all false first, then
// all true) to your firstTrue. Write firstTrue below. The task is described in the box above the editor.

export function firstTrue(n, pred) {
  // Your code here. The task is described in the box above the editor.
}

export function firstTrueFlags(flags) {
  return firstTrue(flags.length, (i) => flags[i]);
}

Ты здесь как гость

Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.

Завести бесплатный аккаунтВойти

Лестница подсказок

Застрял? Открывай по одной, но сначала попробуй сам.

    НазадПоиск элемента в отсортированном списке делением пополамДалееБинарный поиск в повёрнутом отсортированном массиве

    Мы используем необходимые куки для работы сайта (вход и язык). Если ты согласишься, мы также загрузим Google Analytics, чтобы видеть, какие страницы читают, и Google reCAPTCHA для защиты форм обратной связи и сообщений об ошибке от спама. Политика конфиденциальности