Сортировка, поиск и обход — Примеры

Пример 1 — Двоичный поиск и список, которому его нельзя давать

Список идентификаторов ищется тысячи раз за запрос, а функция ниже сканирует его. Скажите, почему такая форма неверна для этой нагрузки, а затем напишите двоичный поиск.

function findIndex(ids: number[], target: number): number {
  for (let i = 0; i < ids.length; i++) {
    if (ids[i] === target) return i;
  }
  return -1;
}

Решение

function findIndex(sorted: number[], target: number): number {
  let low = 0, high = sorted.length - 1;
  while (low <= high) {
    const mid = low + ((high - low) / 2 | 0);
    if (sorted[mid] === target) return mid;
    sorted[mid] < target ? low = mid + 1 : high = mid - 1;
  }
  return -1;
}

// отсортировано [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], искомое 23
// mid 4 (16) -> mid 7 (56) -> mid 5 (23): найдено за 3 сравнения

Деление диапазона вдвое находит значение среди миллиона отсортированных идентификаторов примерно за двадцать сравнений, поэтому с ростом списка стоимость перестаёт быть важной — но теперь функция требует отсортированного входа, а неотсортированный список молча возвращает неверный ответ. Ловушка здесь в обновлении границ: low <= high вместе с mid + 1 и mid - 1 гарантирует продвижение, и ослабление любого из них зацикливает поиск навсегда на значении, которого нет.

Пример 2 — Обход, который зацикливается навсегда

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

function walk(start: Node, seen: Set<Node> = new Set()): void {
  for (const next of start.dependencies) {
    if (seen.has(next)) continue;
    seen.add(next);
    walk(next, seen);
  }
}

// граф: a -> b, b -> c, c -> a
// walk(a) -> walk(b) -> walk(c) -> walk(a) -> ...

Решение

function walk(start: Node, seen: Set<Node> = new Set([start])): void {
  for (const next of start.dependencies) {
    if (seen.has(next)) continue;
    seen.add(next);        // записываем при входе
    walk(next, seen);
  }
}

// walk(a): a уже записан, поэтому c -> a пропускается и обход завершается.

Множество в исходной версии обновляется только после того, как узел достигнут, поэтому a входит второй раз прежде, чем что-либо успевает его записать, и цикл рекурсивно повторяется, пока стек не переполнится. Засеять множество стартовым узлом и записывать каждого соседа перед спуском — тогда каждый узел посещается не более одного раза. Ловушка в том, что исходная версия завершается на ациклическом графе, а это единственная форма, которая встречается в небольшом тесте.