Поиск и сортировка

Технический фундамент операций над коллекциями

Перед реализацией поиска/сортировки важно зафиксировать:

какой тип ключа и сравнения используется (число, строка, дата);
нужна ли стабильность сортировки;
допустима ли мутация исходного массива;
как часто операция выполняется и можно ли кешировать индекс.

Эти параметры влияют на выбор алгоритма больше, чем "любимый метод".

Почему это важно для продуктового кода

Поиск и сортировка встречаются везде: список товаров, таблица заказов, автодополнение, рейтинг, лог событий. Если делать это неаккуратно, интерфейс начинает тормозить, а пользователи видят некорректный порядок данных.

Ключевой момент: выбор алгоритма поиска и сортировки влияет и на скорость, и на правильность бизнес-логики.

Проверь себя: почему сортировка строк без явного компаратора может дать "странный" порядок чисел?

Поиск: линейный и через индекс

Линейный поиск (O(n)) проходит массив до совпадения.

function findById(items, id) {
  return items.find((item) => item.id === id);
}

Это нормально для небольших массивов. Но если поиск частый и данных много, лучше заранее построить индекс через Map.

const byId = new Map(items.map((item) => [item.id, item]));
const target = byId.get(42); // близко к O(1)

Смотри, что важно: быстрый поиск обычно требует дополнительной памяти под индекс.

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

Если массив уже отсортирован, можно использовать бинарный поиск (O(log n)).

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

Смотри, что важно: иногда нужен не "найти точное совпадение", а найти позицию вставки (lower bound): индекс первого элемента, который >= value. Это полезно для диапазонов, авто-дополнения и поиска ближайшего значения.

function lowerBound(arr, value) {
  let left = 0;
  let right = arr.length; // right - exclusive

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < value) left = mid + 1;
    else right = mid;
  }

  return left;
}

Мини-идея для "ближайшего значения": найди i = lowerBound(sorted, budget), затем сравни sorted[i] и sorted[i - 1] (если они существуют).

Здесь часто путаются: бинарный поиск на неотсортированном массиве даст неверный результат.

Проверь себя: почему проверка "массив точно отсортирован" критична перед бинарным поиском?

Сортировка в JavaScript: `sort` и компаратор

По умолчанию Array.prototype.sort() сортирует элементы как строки.

const nums = [1, 20, 3];
console.log(nums.sort()); // [1, 20, 3] как строки

Для чисел нужен компаратор:

nums.sort((a, b) => a - b); // по возрастанию
nums.sort((a, b) => b - a); // по убыванию

Для объектов:

products.sort((a, b) => a.price - b.price);

Смотри, что важно: компаратор должен возвращать:

< 0, если a должно быть раньше b;
> 0, если a должно быть позже b;
0, если элементы равны по правилу сортировки.

Если сортировка по нескольким полям, добавляй "tie-breaker" (вторичное правило), чтобы порядок был предсказуемым.

// Сначала по price, а если price равны - по title
products.sort((a, b) => (a.price - b.price) || a.title.localeCompare(b.title));

Ключевой момент: sort мутирует исходный массив.

const sorted = [...products].sort((a, b) => a.price - b.price);

Дополнительный пример: компаратор для строк с учетом локали.

const names = ['Ёлка', 'Арбуз', 'Яблоко'];
names.sort((a, b) => a.localeCompare(b, 'ru'));
console.log(names);

Реальные микро-сценарии

Список заказов.

Сортировка по дате (createdAt) и быстрый поиск заказа по id через Map.

Каталог товаров.

Сортировка по цене/рейтингу, затем фильтрация и пагинация.

Админ-панель логов.

Быстрый поиск по ключу + сортировка по приоритету ошибки.

Частые ошибки новичков

Использовать sort() без компаратора для чисел.
Применять бинарный поиск к неотсортированным данным.
Забывать, что sort изменяет исходный массив.
Делать слишком частые полные сортировки вместо частичных обновлений.

Анти-провал: перед сортировкой всегда уточни правило порядка в бизнес-терминах (число, дата, строка, локаль).

Что будет, если изменить входные данные

Если в массиве цен появятся строки ('100', '20'), компаратор a - b может отработать благодаря приведению типов, но логика станет хрупкой. Лучше нормализовать данные заранее. Иначе в edge case ('N/A') сортировка сломается.

Проверь себя: почему в прод-коде полезно валидировать типы до сортировки?

Краткий итог

Поиск и сортировка напрямую влияют на UX и производительность.
Для частого поиска по ключу полезен индекс через Map.
Бинарный поиск эффективен только на отсортированных данных.
sort требует явного компаратора для чисел и объектов.
Контроль мутаций и типов данных критичен для предсказуемого результата.

Поиск и сортировка