Бинарный поиск локализованных данных

Intl API (ECMAScript Internationalization API) обеспечивает стандартизированный набор инструментов для локализации в JavaScript, включая сравнение строк, форматирование дат и чисел, а также работу с локалью пользователя. Одной из менее очевидных, но практически значимых областей применения становится реализация бинарного поиска в локализованных данных, где порядок элементов определяется не ASCII-сортировкой, а правилами конкретного языка.

Классический бинарный поиск предполагает строго определённое условие: массив отсортирован по одному и тому же компаратору, который используется во время поиска. В случае локализации это условие усложняется, поскольку порядок строк зависит от языка, регистра, диакритики и культурных правил сравнения.

Обычное лексикографическое сравнение:

  • не учитывает особенности алфавитов (например, немецкое ß или французские акценты)
  • даёт некорректный порядок для пользователей
  • несовместимо между локалями

Поэтому ключевым элементом становится Intl.Collator, который формирует корректную функцию сравнения:

  • учитывает локаль (locale)
  • учитывает уровень чувствительности (sensitivity)
  • поддерживает числовую сортировку (numeric)
  • оптимизирован для повторного использования

Сортировка как обязательное условие бинарного поиска

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

Типичный этап подготовки данных:

const collator = new Intl.Collator("ru", {
  sensitivity: "base"
});

const data = ["яблоко", "ёж", "арбуз", "груша"];

data.sort((a, b) => collator.compare(a, b));

Здесь важно, что сортировка выполняется не стандартным localeCompare, а через Intl.Collator, поскольку он позволяет:

  • переиспользовать один экземпляр для ускорения
  • контролировать параметры сравнения
  • избежать лишних аллокаций строкового метода

Компаратор как основа алгоритма поиска

Бинарный поиск в локализованном контексте не отличается по структуре, но полностью зависит от функции сравнения:

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const comparison = collator.compare(arr[mid], target);

    if (comparison === 0) {
      return mid;
    }

    if (comparison < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Ключевой момент заключается в том, что collator.compare заменяет все предположения о порядке строк. В отличие от обычного < или >, он возвращает значения, соответствующие правилам локали.

Sensitivity и влияние на структуру поиска

Параметр sensitivity в Intl.Collator определяет, какие различия считаются значимыми:

  • base — игнорируются диакритика и регистр
  • accent — учитываются диакритические знаки
  • case — учитывается регистр
  • variant — полное различие символов

Эти настройки напрямую влияют на бинарный поиск, поскольку меняют поведение сравнения.

Пример:

const collator = new Intl.Collator("fr", {
  sensitivity: "base"
});

В таком режиме строки "e", "é", "E" считаются равными с точки зрения поиска, что приводит к необходимости учитывать возможность нескольких совпадений и расширения результата за пределы первого найденного индекса.

Числовая сортировка и смешанные данные

Опция numeric: true изменяет поведение сравнения так, что числа внутри строк сортируются по числовому значению:

const collator = new Intl.Collator("en", {
  numeric: true
});

Это критично для данных вида:

  • “file2”
  • “file10”
  • “file1”

Без numeric: true порядок будет лексикографическим, что ломает бинарный поиск в пользовательских интерфейсах файловых списков, каталогов и логов.

Предвычисление ключей сортировки

Для повышения производительности часто используется стратегия предвычисления сортировочных ключей:

const collator = new Intl.Collator("ru");

const decorated = data.map(item => ({
  value: item,
  key: collator.compare.bind(collator, item)
}));

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

Бинарный поиск по нормализованным данным

Локализация часто связана с Unicode-нормализацией. Строки могут выглядеть одинаково, но иметь разное внутреннее представление:

  • составные символы
  • комбинированные диакритики
  • разные кодовые точки

Перед сортировкой и поиском данные должны быть приведены к единой форме:

function normalize(str) {
  return str.normalize("NFC");
}

Использование нормализации до передачи в Intl.Collator предотвращает ситуации, когда бинарный поиск не находит существующий элемент из-за различий в представлении строки.

Стабильность порядка и побочные эффекты локалей

Разные локали могут давать различный порядок одного и того же набора данных. Например:

  • в одной локали “a” < “ä”
  • в другой “ä” < “a”

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

Производительность и кэширование Collator

Создание Intl.Collator — операция сравнительно дорогая. В высоконагруженных сценариях применяется кэширование:

const collators = new Map();

function getCollator(locale) {
  if (!collators.has(locale)) {
    collators.set(locale, new Intl.Collator(locale, { sensitivity: "base" }));
  }
  return collators.get(locale);
}

Это особенно важно при множественных бинарных поисках в больших массивах, например:

  • автодополнение
  • поиск в словарях
  • индексация каталога товаров

Границы применимости бинарного поиска в локализованных структурах

Несмотря на корректную реализацию через Intl.Collator, бинарный поиск имеет ограничения:

  • не подходит для динамически изменяемых массивов без пересортировки
  • плохо сочетается с частичными совпадениями (prefix search)
  • требует строгой согласованности компаратора на всех этапах

В локализованных системах часто применяется гибридный подход:

  • префиксный поиск через trie или inverted index
  • бинарный поиск для точных совпадений
  • дополнительная фильтрация после первичного поиска

Сравнение с localeCompare

Метод String.prototype.localeCompare является обёрткой над Intl.Collator, но:

  • менее эффективен при массовых операциях
  • создаёт временные объекты при каждом вызове
  • хуже контролируется при тонкой настройке

Использование Intl.Collator позволяет отделить создание стратегии сравнения от её применения, что критично для бинарного поиска.

Ошибки реализации и типичные ловушки

При реализации бинарного поиска в локализованных данных часто возникают следующие проблемы:

  • сортировка и поиск используют разные настройки локали
  • данные не нормализованы перед сравнением
  • collator создаётся внутри цикла поиска
  • смешиваются разные уровни sensitivity
  • предполагается транзитивность при несовместимых настройках

Любое нарушение этих условий делает бинарный поиск некорректным, даже если алгоритм формально реализован правильно.

Применение в реальных системах

Локализованный бинарный поиск используется в:

  • поисковых автокомплитах
  • словарях и энциклопедиях
  • UI-компонентах выбора (dropdown, select)
  • файловых менеджерах
  • CRM и каталогах с мультиязычными данными

Во всех этих системах ключевым фактором является не скорость самого поиска, а корректность культурного порядка, задаваемого Intl.Collator.

Оглавление