Сортировки и бинарный поиск
Писать сортировки почти никогда не просят - спрашивают их свойства и умение выбрать: стабильность, память, худший случай. А вот бинарный поиск просят писать регулярно и ловят на границах. Он умещается в двадцать строк, и багов в нём живёт больше, чем в ином сервисе.
Типовые формулировки: «чем quicksort хуже mergesort?», «найди элемент в повёрнутом массиве», «минимальная скорость, чтобы успеть за h часов».
// Фирменный мидловый вопрос - бинарный поиск по ответу. Узнал его в задаче - считай, секция пройдена; не узнал - будешь честно перебирать варианты и не уложишься.
Зоопарк сортировок и что из него берут
Есть доказанная нижняя граница: сортировка, основанная на сравнениях, не может быть быстрее O(n log n). Интуиция за доказательством такая - у n элементов есть n! возможных порядков, каждое сравнение делит множество вариантов пополам, значит сравнений нужно хотя бы log₂(n!), а это и есть примерно n log n. Обойти границу можно только отказавшись от сравнений: counting и radix sort раскладывают элементы по значениям и работают за O(n), но требуют ограниченного диапазона ключей.
Классика и её размены. Quicksort: в среднем O(n log n), в худшем O(n²) на неудачном выборе опорного элемента, работает in-place, нестабильна. Mergesort: гарантированные O(n log n), стабильная, но требует O(n) дополнительной памяти. Heapsort: O(n log n) гарантированно и in-place, зато нестабильная и на практике медленнее из-за прыжков по памяти.
Встроенная сортировка в Python и Java для объектов - Timsort, гибрид merge и вставок. Он стабилен, даёт O(n log n) в худшем случае и почти O(n) на частично упорядоченных данных, которых в реальной жизни большинство.
// Задача «найди k-й по величине» - не задача на сортировку. Куча размера k решает её за O(n log k), а quickselect - в среднем за O(n). Отсортировать весь массив ради одного элемента значит переплатить.
- стабильность
- равные элементы сохраняют исходный взаимный порядок. Критично при сортировке по нескольким полям подряд: сначала по имени, потом по городу - и внутри города имена остаются упорядоченными
Бинарный поиск без багов
Бинарному поиску нужна не отсортированность как таковая, а монотонность. Представь функцию-проверку, которая для каждого элемента отвечает «да» или «нет» - её называют предикатом. Монотонность означает, что ответы идут двумя сплошными блоками: сначала все «нет», потом все «да». Бинарный поиск ищет ровно границу между блоками, и отсортированный массив - лишь частный случай такой картины.
Работает он делением пополам: миллиард элементов превращается в пятьсот миллионов, потом в двести пятьдесят, и через тридцать шагов остаётся один. Отсюда и O(log n).
Шаблон, который не багует. Держи полуинтервал [lo, hi): левый край включён, правый нет. Середина считается как lo + (hi − lo) / 2. На каждом шаге сохраняется инвариант «ответ лежит внутри». Цикл останавливается, когда lo сравнялся с hi. Смешаешь в одном коде полуинтервал [lo, hi) и отрезок [lo, hi] - получишь либо вечный цикл, либо промах на единицу.
// Форма lo + (hi − lo)/2 вместо (lo + hi)/2 - не пижонство: в Java и C++ сумма двух больших индексов переполняет целочисленный тип и становится отрицательной. В Python переполнения нет, но упомянуть это на собесе стоит, потому что вопрос дежурный.
Бинарный поиск по ответу
Самый ценный приём темы. Иногда искать надо не элемент в массиве, а само значение ответа - и вот тут бинарный поиск разворачивается в полную силу.
Задача звучит так: «какая минимальная скорость поедания бананов, чтобы успеть за h часов». Прямого массива тут нет. Зато есть проверка: для конкретной скорости легко посчитать, успеваем или нет. И у этой проверки есть монотонность - если скорости v хватает, то v+1 хватает тем более. Значит ответы выстроены как «нет, нет, нет, да, да», и граница ищется бинарным поиском по диапазону возможных скоростей.
Опознавательный знак в условии: «найди минимальное X, при котором возможно Y» плюс ощущение, что при большем X точно станет только легче. Дальше пишешь функцию-проверку и бинаришь не по массиву, а по пространству ответов.
// Повёрнутый отсортированный массив - другой родственник той же идеи. На каждом шаге одна из половин гарантированно отсортирована: сравни середину с краем, пойми какая именно, и проверь, попадает ли искомое в её диапазон.
- предикат
- функция, отвечающая «да» или «нет». В бинарном поиске по ответу это проверка выполнимости при конкретном значении параметра
Как отвечать: «Отсортированный массив повернули вокруг неизвестной точки. Найди элемент»
Модифицированный бинарный поиск за O(log n). Ключевое наблюдение: как бы массив ни повернули, на каждом шаге хотя бы одна из половин остаётся отсортированной. Сравниваю значение на левом краю со значением в середине: если левое не больше среднего, отсортирована левая половина. Дальше проверяю, попадает ли искомое в диапазон этой отсортированной половины: попадает - иду в неё, не попадает - в другую. Держу строгий инвариант полуинтервала, потому что повёрнутые массивы особенно любят промахи на единицу. И сразу уточню про дубликаты: если они возможны, случай «край равен середине» неразрешим без сдвига границы на один, и худший случай деградирует до O(n).
Назван приём, названа причина, по которой он работает, и добровольно разобран случай с дубликатами. Последнее обезвреживает встречный вопрос интервьюера до того, как он прозвучал.
На чём валят
- −Писать (lo + hi) / 2 в языке с фиксированной разрядностью: сумма переполняется и становится отрицательной.
- −Смешивать в одном коде инварианты [lo, hi] и [lo, hi): вечный цикл или промах на единицу.
- −Утверждать «quicksort всегда быстрее»: на маленьких и почти упорядоченных массивах вставки быстрее, и Timsort именно поэтому их и использует.
- −Запускать бинарный поиск по неотсортированным данным: он не падает, а молча возвращает мусор.
- −Сортировать весь массив, когда нужен один k-й элемент.
Проверьте себя
Пять вопросов из банка по этой подтеме. Всего их 18, остальные разбираются в тренажёре.
- Merge sort стабилен и всегда O(n log n), но для массивов в памяти часто берут quicksort. Почему?A)Merge sort требует O(n) доп. памяти и хуже по локальности кэша, а quicksort сортирует на месте с меньшей константойB)Merge sort работает за O(n²)C)Quicksort стабилен, а merge sort нетD)Merge sort не умеет сортировать числа
показать ответ и разбор
+A)Merge sort требует O(n) доп. памяти и хуже по локальности кэша, а quicksort сортирует на месте с меньшей константой// разбор: Merge sort гарантирует O(n log n) и стабильность, но сливает через дополнительный буфер O(n) и прыгает по памяти хуже quicksort. Quicksort сортирует in-place, у него меньше константа и лучше локальность кэша, поэтому в среднем он быстрее по времени стены. Introsort = quicksort со страховкой heapsort при плохом разбиении. Merge sort зато незаменим для внешней сортировки и связных списков.
- Бинарный поиск можно применять не только к массиву, но и «по ответу» (binary search on answer). Что это делает возможным?A)Наличие в данных ровно 2ⁿ элементовB)То, что ответ — простое числоC)Монотонность предиката: если значение X подходит, то и все большие (или меньшие) — тоже, и диапазон ответов можно делить пополамD)То, что функция непрерывна и дифференцируема
показать ответ и разбор
+C)Монотонность предиката: если значение X подходит, то и все большие (или меньшие) — тоже, и диапазон ответов можно делить пополам// разбор: Binary search on answer ищет минимальное/максимальное значение параметра, удовлетворяющее условию, когда условие монотонно по параметру: feasible(X) истинно для X ≥ X₀ (или ≤). Тогда пространство ответов делят пополам, проверяя feasible(mid). Пример: минимальная скорость/вместимость, при которой задача выполнима. Ключ — монотонность, а не сам массив.
- Отсортированный массив из 1 000 000 элементов. Сколько примерно сравнений сделает бинарный поиск в худшем случае?A)около 20B)около 1 000C)около 500 000D)около 1 000 000
показать ответ и разбор
+A)около 20// разбор: Каждое сравнение отбрасывает половину оставшегося диапазона: 1 000 000 → 500 000 → … → 1, всего log₂(n) ≈ 20 шагов. Логарифм растёт мучительно медленно: на миллиарде элементов — всего ~30 сравнений. Интуиция «log n — сколько раз можно поделить пополам» выручает в вопросах про деревья и сортировки.
- Нужно один раз найти число в неотсортированном массиве. Стоит ли сначала отсортировать его ради бинарного поиска?A)да — бинарный поиск окупит сортировку уже на первом запросеB)нет — один проход O(n) дешевле сортировки O(n log n)C)да — после сортировки поиск станет O(1)D)нет — бинарный поиск работает и без сортировки
показать ответ и разбор
+B)нет — один проход O(n) дешевле сортировки O(n log n)// разбор: Один поиск — линейный проход за O(n). Сортировка стоит O(n log n) и окупается, только когда поисков много: k запросов бинарным поиском — O(n log n + k·log n) против O(k·n) перебором. Это общий паттерн собеса «предобработка против разового прохода»: сначала спроси, сколько раз будем искать.
- Список заказов сортируют по городу, а внутри города — по сумме заказа. Что для этого нужно?A)Отсортировать по сумме, затем ещё раз по городу — если сортировка стабильнаяB)Отсортировать по городу, потом по сумме — порядок проходов роли не играетC)Отсортировать по сумме и по городу независимо, затем склеить два результатаD)Такой порядок одной сортировкой не получить, нужна группировка по городам
показать ответ и разбор
+A)Отсортировать по сумме, затем ещё раз по городу — если сортировка стабильная// разбор: Стабильная сортировка не переставляет элементы с равными ключами. Поэтому сортируют сначала по вторичному ключу (сумме), а затем по первичному (городу): внутри каждого города прежний порядок по сумме сохранится. Порядок проходов обратный ожидаемому, и в этом вся суть приёма. Альтернатива — сортировать один раз по составному ключу (город, сумма), как это делает ORDER BY в SQL.
дальше
Теорию прочитали. Навык ставится повторением
В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.