Конспект раздела: поиск и порядковые статистики

Карта раздела

Раздел отвечает на два вопроса: «как быстро найти нужное в упорядоченных данных» и «как получить элемент нужного РАНГА, не сортируя всё». Обе главы про одно - не делать лишней работы.

двоичный поиск       ->  инвариант [lo, hi); левая/правая граница = один код с знаком;
     |                    поиск по МОНОТОННОМУ ответу (искать не элемент, а число)
выбор k-го           ->  порядковая статистика без полной сортировки;
                          quickselect Θ(n) в среднем; рандомизация; медиана медиан Θ(n)

Общая мысль обеих глав - «выбрось часть, где ответа заведомо нет»: двоичный поиск выбрасывает ровно половину, quickselect - часть после разбиения вокруг опорного: в среднем заметную долю, а при неудачном опорном лишь один элемент - отсюда его худший Θ(n²).

Шаблоны двоичного поиска, которые не ломаются

Весь набор - ОДИН каркас с инвариантом полуинтервала [lo, hi); меняется один знак или одна ветка.

нужно	сдвиг	ответ `lo == hi`
найти сам `x`	ветка `== x` → выход	индекс вхождения или «нет»
левая граница (`lower_bound`)	`a[mid] < x → lo = mid+1`	первый `≥ x` (место вставки)
правая граница (`upper_bound`)	`a[mid] <= x → lo = mid+1`	первый `> x` (за концом блока)
число вхождений `x`	правая − левая	длина блока за `Θ(log n)`
поиск по ответу	`ok(mid)` вместо `a[mid]`	порог по монотонному предикату

Три правила, чтобы поиск не ломался: (1) mid = lo + (hi − lo)//2 - и середина всегда в участке, и нет переполнения суммы; (2) lo = mid + 1 (с плюс-единицей - иначе зависание), а hi = mid (без, правый конец и так не входит); (3) знак сравнения выбирает границу: строгий < тянет к левому краю блока, нестрогий ≤ уводит за правый.

Сводная таблица выбора k-го элемента

способ	худший случай	память	заметка
`k` раз найти минимум	`Θ(n²)` для медианы	`O(1)`	наивнее всего
полная сортировка + `a[k−1]`	`Θ(n·log n)`	зависит от сортировки	избыточно ради одного
quickselect, случайный опорный	`Θ(n)` в ожидании	`O(1)` на месте	стандарт на практике
медиана медиан (BFPRT)	`Θ(n)` гарантированно	`O(1)` на месте	теория; большая константа

Главный сдвиг мышления

Двоичный поиск учит переходу от «искать в массиве» к «искать в ПРОСТРАНСТВЕ ОТВЕТОВ»: если задача просит минимальное/максимальное «такое, что…», а проверить конкретную догадку легко, сведи её к монотонному предикату ok(x) и получи log(диапазон) вместо перебора.

Выбор учит другому: чтобы узнать элемент нужного РАНГА, не нужен порядок всех остальных. Полная сортировка находит сразу n порядковых статистик, а нам нужна одна - плата за n − 1 ненужных. Разбил, сравнил k с рангом опорного, отбросил половину - и n·log n стало n. А рандомизация опорного - первый пример общего приёма: детерминированный алгоритм уязвим к подстроенному входу, добавь случайность внутрь - и источник неудачи переедет с данных на монетку.

Ловушки джокера всего раздела

lo = mid вместо lo = mid + 1 - зависание двоичного поиска (hi − lo не убывает).

Перепутал < и ≤ - получил не ту границу; по виду кода не заметно.

Применил поиск по ответу к немонотонному предикату - молча неверный ответ; сначала докажи ступеньку нет→да.

Спутал медиану со средним - «типичное» значение, изуродованное выбросами.

Промах на один: k-я статистика (с 1) - это a[k−1] (с 0).

Фиксированный опорный quickselect в проде - Θ(n²) на отсортированных данных; бери случайный.

Группы по 3 в медиане медиан - сумма долей ровно 1, скат к Θ(n·log n).

Проверь себя

Почему lo = mid + 1, а hi = mid - без плюс-единицы?

Чем в коде отличается левая граница от правой и к какому краю блока прилипает каждая?

Что нужно, чтобы применить двоичный поиск по монотонному ответу, и что он экономит?

Откуда у quickselect средняя Θ(n) и худшая Θ(n²), и как их лечат рандомизация и медиана медиан?

Почему в медиане медиан группы именно по 5?