Что нужно сделать с массивом чтобы алгоритмическая сложность поиска элемента была логарифмической?

O(log n) поиск в массиве: сортировка и двоичный поиск

Для достижения логарифмической сложности поиска элемента в массиве нужно выполнить один ключевой шаг — отсортировать массив, а затем использовать двоичный поиск (binary search).

Шаг 1: Сортировка массива

Первое требование для O(log n) поиска — массив должен быть отсортирован (в возрастающем или убывающем порядке).

// Исходный массив
const unsorted = [15, 3, 9, 1, 7, 14, 5, 2];

// После сортировки
const sorted = unsorted.sort((a, b) => a - b);
console.log(sorted); // [1, 2, 3, 5, 7, 9, 14, 15]

Сложность сортировки: O(n log n) для большинства алгоритмов (merge sort, quick sort, heap sort).

Шаг 2: Двоичный поиск

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

1. Начни с середины массива
2. Если элемент в середине — нашли!
3. Если искомое меньше середины — ищи в левой половине
4. Если больше — ищи в правой половине
5. Повторяй, пока не найдёшь или массив не станет пустым

// Реализация двоичного поиска
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; // Не найден
}

const sorted = [1, 2, 3, 5, 7, 9, 14, 15];
console.log(binarySearch(sorted, 7)); // 4 (индекс найденного элемента)
console.log(binarySearch(sorted, 10)); // -1 (не найден)

Как это работает пошагово

Поиск элемента 7 в массиве [1, 2, 3, 5, 7, 9, 14, 15]:

Шаг 1: left=0, right=7, mid=3
  arr[3] = 5 < 7 → left=4

Шаг 2: left=4, right=7, mid=5
  arr[5] = 9 > 7 → right=4

Шаг 3: left=4, right=4, mid=4
  arr[4] = 7 ✓ Найден!

Всего 3 итерации вместо линейного поиска (до 8)

Сложность

• Сортировка: O(n log n)
• Двоичный поиск: O(log n)
• Общая сложность один раз: O(n log n) + O(log n) = O(n log n)

Но если ты часто ищешь в одном массиве:

// Один раз отсортировали — O(n log n)
const sorted = arr.sort((a, b) => a - b);

// Потом множество поисков — каждый O(log n)
for (let i = 0; i < 1000; i++) {
  binarySearch(sorted, randomValue);
}
// 1000 * O(log n) = 1000 * O(log n) — очень эффективно!

Сравнение: линейный vs двоичный поиск

// Линейный поиск — O(n)
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Для массива из 1 000 000 элементов:
// - Линейный поиск в худшем случае: 1 000 000 операций
// - Двоичный поиск в худшем случае: ~20 операций (log2(1000000) ≈ 20)

Встроенные методы JavaScript

// Если массив отсортирован, используй встроенные методы
const sorted = [1, 2, 3, 5, 7, 9, 14, 15];

// indexOf() — O(n), НЕ рекомендуется для больших отсортированных массивов
console.log(sorted.indexOf(7)); // 4

// Для O(log n) нужна своя реализация binary search

Условие работы двоичного поиска

1. Массив должен быть отсортирован — обязательное условие!
2. Сравнение элементов должно быть определено — элементы должны быть сравнимы
3. Иммутабельность не требуется — двоичный поиск работает с отсортированным массивом как есть

Практический пример

// Ищем пользователя по ID в больших данных
const users = [
  { id: 1, name: 'Alice' },
  { id: 5, name: 'Bob' },
  { id: 10, name: 'Charlie' },
  { id: 15, name: 'David' },
];

function binarySearchByProperty(arr, target, prop) {
  let left = 0, right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid][prop] === target) return arr[mid];
    if (arr[mid][prop] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return null;
}

const result = binarySearchByProperty(users, 10, 'id');
console.log(result); // { id: 10, name: 'Charlie' }

Резюме

Чтобы получить O(log n) поиск:

1. Отсортируй массив — один раз перед поиском
2. Используй двоичный поиск — log n операций на каждый поиск
3. Это стоит, если собираешься делать много поисков в одном массиве

Для небольших массивов или редких поисков линейный поиск может быть проще и достаточно быстро. Выбирай подход в зависимости от размера данных и частоты поисков.