Алгоритмы с нуля
Сортировка и поиск: чтение кода
Суть Читаем реальные сниппеты сортировки и поиска — ошибки на единицу в binary search, partition Lomuto, stable-слияние и quickselect — предсказываем баг или поведение и выбираем фикс.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеБаги сортировки и поиска прячутся на границах: не то сравнение, половина, отброшенная на индекс дальше нужного, swap, теряющий stable-свойство. Читайте каждый сниппет как на ревью и называйте дефект — или точное поведение — прежде чем выбрать.
Цель
Отработайте цикл ревьюера для этого юнита: проследите инвариант в голове, найдите ошибку на единицу или потерянную гарантию и выберите минимальный корректный фикс.
Сниппет 1 — бесконечный цикл
function bsearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid; // отбрасываем левую часть
else hi = mid - 1; // отбрасываем правую часть
}
return -1;
} Викторина
Completed
На многих входах это зависает навсегда. В чём баг и каков фикс?
Heads-up lo <= hi корректно для включающего диапазона — именно оно позволяет проверить финальный диапазон из одного элемента. Зависание из-за того, что lo = mid не продвигается, а не из-за условия.
Heads-up Направление округления тут ни при чём. При lo = mid диапазон не сужается при любом округлении. Фикс — lo = mid + 1.
Heads-up Порядок проверок не вызывает бесконечный цикл. Дефект — обновление границы lo = mid, которое не даёт прогресса.
Сниппет 2 — переполнение в вычислении середины
int bsearch(int arr[], int n, int target) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2; // <-- здесь
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
} Викторина
Completed
Это проходило все маленькие тесты, но портило результаты на многогигабайтном отсортированном массиве из 32-битных int. Почему и каков канонический фикс?
Heads-up Можно; алгоритм в порядке. Единственный дефект — переполнение суммы lo + hi в 32-битном int. Считайте mid = lo + (hi - lo) / 2.
Heads-up lo <= hi корректно и читает только валидные индексы. Баг — арифметическое переполнение (lo + hi), а не граница цикла.
Heads-up Усечение в сторону lo — именно то, чего binary search и ожидает, и здесь безвредно. Реальный дефект — переполнение lo + hi на больших индексах.
Сниппет 3 — partition Lomuto
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
} Викторина
Completed
Что гарантирует возвращаемый индекс и почему эта схема делает quicksort не stable?
Heads-up Он возвращает место, куда сел выбранный pivot после partition, то есть его отсортированную позицию — а не медиану, если только pivot не оказался медианой. Поиск медианы — это quickselect, другое применение partition.
Heads-up Partition гарантирует порядок относительно pivot, а не баланс. Экстремальный pivot оставляет одну сторону пустой — это худший случай O(n²). Баланс даёт хороший выбор pivot.
Heads-up Рекурсия не имеет отношения к stable-свойству. Нестабильность из-за swap'ов, перемещающих равные элементы через границу pivot и теряющих исходный относительный порядок.
Сниппет 4 — quickselect для k-го наименьшего
function quickselect(arr, k, lo = 0, hi = arr.length - 1) {
const p = partition(arr, lo, hi); // финальный индекс pivot
if (p === k) return arr[p];
if (p < k) return quickselect(arr, k, p + 1, hi);
return quickselect(arr, k, lo, p - 1);
} Викторина
Completed
Quickselect находит k-й наименьший элемент, переиспользуя partition. Какова его сложность и почему это лучше полной сортировки для этой задачи?
Heads-up Сортировка обрабатывает обе стороны на каждом уровне; quickselect рекурсирует только в сторону с k, давая в среднем O(n). В этом весь смысл выбора вместо сортировки.
Heads-up Каждый partition всё равно сканирует O(n) элементов, так что один уровень линеен. Геометрическая сумма односторонней рекурсии — O(n) в среднем, а не O(log n).
Heads-up Quickselect намеренно работает на неотсортированном входе — partition не нужна отсортированность. Худший случай O(n²) на плохих pivot чинится рандомизацией или median-of-medians.
Итог
Каждый дефект здесь живёт на границе: binary search должен сужать диапазон (lo = mid + 1, никогда lo = mid) и считать mid = lo + (hi - lo) / 2, чтобы обойти переполнение; partition Lomuto возвращает финальную отсортированную позицию pivot и не stable, потому что swap’ы пересекают равные ключи; а quickselect переиспользует этот partition, находя k-й элемент за O(n) в среднем рекурсией только в одну сторону. Сначала читайте инвариант — тогда фикс обычно в один токен.