Алгоритмы и сложность: O(n) без страха

// Считаем не миллисекунды, а шаги — число сравнений
const range = (n) => Array.from({ length: n }, (_, i) => i);

// O(n): в худшем случае просматриваем все элементы
function linearSteps(list, target) {
  let steps = 0;
  for (const value of list) {
    steps++;
    if (value === target) break;
  }
  return steps;
}

// O(n²): каждый элемент сравниваем с каждым
function pairSteps(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) steps++;
  }
  return steps;
}

// O(log n): каждый шаг отбрасывает половину отсортированного массива
function binarySteps(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  let steps = 0;
  while (low <= high) {
    steps++;
    const middle = Math.floor((low + high) / 2);
    if (sorted[middle] === target) break;
    if (sorted[middle] < target) low = middle + 1;
    else high = middle - 1;
  }
  return steps;
}

const sizes = [10, 1000, 100000];
console.log(sizes.map((n) => linearSteps(range(n), -1))); // [ 10, 1000, 100000 ]
console.log(sizes.map((n) => binarySteps(range(n), -1))); // [ 3, 9, 16 ]
console.log(sizes.slice(0, 2).map((n) => pairSteps(n))); // [ 100, 1000000 ]

/**
 * Бинарный поиск в массиве, отсортированном по возрастанию.
 * Возвращает индекс найденного элемента или -1. Сложность — O(log n).
 */
export function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    const value = sorted[middle];

    if (value === target) return middle;
    if (value < target) low = middle + 1; // искомое правее середины
    else high = middle - 1; // искомое левее середины
  }

  return -1;
}

import { test } from "node:test";
import assert from "node:assert/strict";
import { binarySearch } from "./binary-search.mjs";

const prices = [490, 900, 1200, 1500, 2300, 4100, 7800];

test("находит первый, средний и последний элемент", () => {
  assert.equal(binarySearch(prices, 490), 0);
  assert.equal(binarySearch(prices, 1500), 3);
  assert.equal(binarySearch(prices, 7800), 6);
});

test("возвращает -1, если элемента нет", () => {
  assert.equal(binarySearch(prices, 100), -1); // меньше всех
  assert.equal(binarySearch(prices, 1000), -1); // между соседями
  assert.equal(binarySearch(prices, 9999), -1); // больше всех
});

test("пустой массив и массив из одного элемента", () => {
  assert.equal(binarySearch([], 5), -1);
  assert.equal(binarySearch([5], 5), 0);
  assert.equal(binarySearch([5], 7), -1);
});

test("совпадает с indexOf на массивах разной длины", () => {
  for (let n = 0; n <= 64; n++) {
    const evens = Array.from({ length: n }, (_, i) => i * 2); // 0, 2, 4, …
    for (let target = -1; target <= n * 2; target++) {
      assert.equal(binarySearch(evens, target), evens.indexOf(target), `n=${n}, target=${target}`);
    }
  }
});

// 1. Без функции сравнения элементы сравниваются как строки
console.log([25, 100, 3].toSorted()); // [ 100, 25, 3 ]
console.log([25, 100, 3].toSorted((a, b) => a - b)); // [ 3, 25, 100 ]

// 2. Строки по кодам UTF-16: «ё» оказывается после «я»
const words = ["яблоко", "ёж", "ель"];
console.log(words.toSorted()); // [ 'ель', 'яблоко', 'ёж' ]
console.log(words.toSorted((a, b) => a.localeCompare(b, "ru"))); // [ 'ёж', 'ель', 'яблоко' ] — по правилам русской сортировки ё идёт вместе с е

// 3. Стабильность (ES2019+): равные элементы сохраняют исходный порядок
const orders = [
  { id: 1, status: "new" },
  { id: 2, status: "paid" },
  { id: 3, status: "new" },
  { id: 4, status: "paid" },
];
const byStatus = orders.toSorted((a, b) => a.status.localeCompare(b.status));
console.log(byStatus.map((order) => order.id)); // [ 1, 3, 2, 4 ]

// 4. Сколько раз вызывается сравнение — деталь реализации V8, не гарантия спецификации
function countComparisons(list) {
  let calls = 0;
  list.toSorted((a, b) => {
    calls++;
    return a - b;
  });
  return calls;
}
let seed = 1;
const random = () => (seed = (seed * 48271) % 2147483647); // воспроизводимые «случайные» числа
const shuffled = Array.from({ length: 1000 }, random);
const alreadySorted = shuffled.toSorted((a, b) => a - b);
console.log(countComparisons(alreadySorted)); // 999
console.log(countComparisons(shuffled)); // 8630

const orders = Array.from({ length: 50000 }, (_, i) => ({ id: 100000 + i, total: (i % 90) * 100 }));
const requested = [100007, 149999, 123456, 999999];

// Без индекса: каждый запрос — find по всему массиву, O(n) на запрос
let scanned = 0;
const viaFind = requested.map((id) =>
  orders.find((order) => {
    scanned++;
    return order.id === id;
  }),
);
console.log(scanned); // 123465 — просмотрено элементов на 4 запроса

// С индексом: один проход O(n) на построение, дальше get в среднем быстрее O(n)
const byId = new Map(orders.map((order) => [order.id, order]));
const viaMap = requested.map((id) => byId.get(id));
console.log(byId.size); // 50000 — индекс занимает память
console.log(viaMap.map((order) => order?.total)); // [ 700, 4900, 5600, undefined ]
console.log(viaFind.every((order, i) => order === viaMap[i])); // true

// 100 000 номеров заказов, каждый тысячный — повтор уже встречавшегося
const ids = Array.from({ length: 100_000 }, (_, i) => (i % 1000 === 999 ? i - 500 : i));

// O(n²): indexOf внутри filter — вложенный цикл, только спрятанный
function duplicatesNaive(list) {
  return list.filter((value, index) => list.indexOf(value) !== index);
}

// O(n): один проход, проверка через Set
function duplicatesWithSet(list) {
  const seen = new Set();
  const duplicates = [];
  for (const value of list) {
    if (seen.has(value)) duplicates.push(value);
    else seen.add(value);
  }
  return duplicates;
}

function measure(label, fn) {
  const start = performance.now();
  const result = fn(ids);
  console.log(`${label}: ${(performance.now() - start).toFixed(1)} мс`);
  return result;
}

const naive = measure("filter + indexOf", duplicatesNaive);
const fast = measure("Set", duplicatesWithSet);
console.log(naive.length, fast.length); // 100 100
console.log(naive.every((value, i) => value === fast[i])); // true

$ node duplicates.mjs
filter + indexOf: 7581.0 мс
Set: 18.4 мс
100 100
true