pattern heroPT–23LeetCode Extension

Бинарный поиск

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

Вариант
P05 Бинарный поискНайти число · 1×

Пример задачи: найти индекс числа 12 в отсортированном массиве [2, 5, 8, 12, 16, 23, 38, 56, 72].

021528312416523638756872lo
ещё в диапазонесередина, проверяемотброшенонайдено

lo — первый индекс, 0

lo = 0hi = –mid = –
01/21
сначала · назад · пуск · шаг
Скорость
1function binarySearch(nums, target):
2 lo = 0
3 hi = len(nums) - 1
4 while lo <= hi: // ends if not found
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < target:
7 lo = mid + 1
8 else if nums[mid] > target:
9 hi = mid - 1
10 else:
11 return mid

← → шаг · пробел — пауза

Как узнать

отсортированный массив, O(log n) в ограничениях или «наименьшее подходящее значение», когда все большие тоже подходят.

Как решать такие задачи

  1. Поставь lo и hi на края диапазона, где может быть ответ.
  2. Посмотри на середину и задай про неё вопрос «да или нет».
  3. Оставь половину, где ответ ещё может быть. Сдвигай lo или hi за mid, чтобы диапазон всегда сужался.
  4. Остановись, когда нашёл. Если lo обогнал hi, ответа нет.

Вариант: Поиск по ответу

То же, но ищем не элемент в массиве, а сам ответ, например наименьшую скорость. Работает, когда любой вариант легко проверить, а проверки идут «нет, нет, …, да, да»: граница между «нет» и «да» и есть ответ.

  1. Как узнать: просят «наименьшее x, такое что ...» (или наибольшее), а проверить одно данное x легко.
  2. Найди границы: lo — наименьшее x, которое может подойти, hi — значение, которое точно подходит, здесь это самая большая кучка.
  3. Напиши feasible(x) — проверку «да или нет» — и убедись, что она монотонна: если для x ответ «да», то и для любого большего x тоже «да».
  4. Повторяй, пока lo < hi: если feasible(mid), ставь hi = mid, чтобы mid остался в диапазоне, иначе lo = mid + 1. Когда они встретятся, lo — самое левое подходящее значение.

Вариант: Повёрнутый массив

То же, но массив повёрнут, будто его разрезали и переставили куски. Если разрезать его посередине, одна половина всё равно отсортирована, и по ней видно, куда идти дальше.

  1. Как узнать: массив «отсортирован, но повёрнут» или сначала растёт, а потом падает, а нужно всё равно O(log n).
  2. На каждом mid найди половину, которой можно верить: сравни nums[lo] и nums[mid] и пойми, какая половина отсортирована.
  3. Проверь, лежит ли цель между краями отсортированной половины. Если да, оставь её, если нет — другую.
  4. Минимум повёрнутого массива ищут так же, сравнивая nums[mid] с nums[hi]: если nums[mid] > nums[hi], спуск и минимум правее mid, иначе на mid или левее.
  5. Пик ищут, сравнивая nums[mid] с соседом nums[mid + 1]: если сосед больше, пик правее, иначе на mid или левее.

Где встречается

  • git bisect. Ищет коммит, который что-то сломал. Берёт коммит посередине между «ещё работало» и «уже сломано», ты его проверяешь, и половина истории отбрасывается. Даже среди 1000 коммитов виновника находят примерно за 10 проверок.
  • Индексы в базах данных. Внутри каждой страницы индекса ключи лежат по порядку, и PostgreSQL находит нужный делением пополам, а не перебором.
  • Python. Модуль bisect находит, куда вставить число в отсортированный список, чтобы порядок не сломался.