Яка складність бінарного пошуку?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Час: O(log n) у середньому і найгіршому випадках; O(1) у найкращому (якщо шуканий елемент - одразу в середині).
Пам'ять: O(1) для ітеративної реалізації; O(log n) для рекурсивної (через стек викликів).
Кількість порівнянь: приблизно ⌈log2 n⌉ (у межах ⌈log2 n⌉...⌈log2 n⌉+1).

Детальний розбір

Передумови застосування

Дані відсортовані за ключем порівняння.
Є випадковий доступ до елементів за O(1) (наприклад, масив/динамічний масив).
Компаратор задає строгий порядок і транзитивний (без суперечностей).

На кожному кроці бінарний пошук ділить поточний діапазон навпіл і відкидає одну з половин. Після k кроків залишається не більше n / 2^k елементів. Зупинка відбувається, коли залишилося 1 або 0 елементів, тобто n / 2^k ≤ 1 ⇒ k ≥ ⌈log2 n⌉. Тому час - O(log n).

Випадки за часом

Найкращий випадок: O(1) - шукане значення одразу в середині.
Середній випадок: O(log n) - усереднення за рівномірним розподілом цільового індексу.
Найгірший випадок: O(log n) - потрібна максимально можлива кількість кроків до звуження діапазону до одиниці.

Пам'ять

Ітеративна реалізація використовує сталу кількість змінних - O(1). Рекурсивна додає вкладеність викликів глибиною близько ⌈log2 n⌉ - O(log n) за пам'яттю.

Код (JavaScript)

javascript

// Ітеративний бінарний пошук: індекс знайденого елемента або -1
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    // Безпечне обчислення середини (захищає від переповнення в мовах з 32-бітними int)
    const mid = left + ((right - left) >> 1);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1; else right = mid - 1;
  }
  return -1;
}

// lowerBound: перший індекс i, де arr[i] >= target
function lowerBound(arr, target) {
  let left = 0, right = arr.length; // напівінтервал [left, right)
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] < target) left = mid + 1; else right = mid;
  }
  return left;
}

// upperBound: перший індекс i, де arr[i] > target
function upperBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] <= target) left = mid + 1; else right = mid;
  }
  return left;
}

// Перший індекс входження target або -1 (для масивів з повторами)
function firstOccurrence(arr, target) {
  const i = lowerBound(arr, target);
  return i < arr.length && arr[i] === target ? i : -1;
}

// Останній індекс входження target або -1
function lastOccurrence(arr, target) {
  const j = upperBound(arr, target) - 1;
  return j >= 0 && arr[j] === target ? j : -1;
}

// Позиція вставки для збереження сортування (якщо елемента немає)
function insertionIndex(arr, target) {
  return lowerBound(arr, target);
}

// Приклади використання
const a = [1, 2, 4, 4, 5, 9, 12];
console.log(binarySearch(a, 5));        // 4
console.log(firstOccurrence(a, 4));     // 2
console.log(lastOccurrence(a, 4));      // 3
console.log(insertionIndex(a, 6));      // 5

Часті помилки і нюанси

Неправильні межі циклу: використовувати узгоджений напівінтервал [l, r) чи замкнутий [l, r] і відповідну умову зупинки.
Обчислення середини як (l + r) / 2 може переповнюватися в мовах з 32-бітними цілими; безпечніше l + (r - l) / 2.
Зациклення при неправильному оновленні меж (наприклад, r = mid замість r = mid - 1 у замкнутому інтервалі).
Дублікати: базовий пошук повертає будь-який знайдений індекс; для першого/останнього входження використовуйте lowerBound/upperBound.
Несортовані дані чи структури без O(1) доступу (наприклад, зв'язні списки) не підходять для класичного бінарного пошуку.

Порівняння з лінійним пошуком

Лінійний пошук - O(n). Бінарний - O(log n). Наприклад, при n = 1 000 000 бінарний пошук робить приблизно 20 кроків, тоді як лінійний може потребувати до мільйона порівнянь.

Підсумок

Бінарний пошук працює за O(log n) за часом і O(1)/O(log n) за пам'яттю (ітеративно/рекурсивно). Це досягається завдяки поетапному діленню діапазону пошуку навпіл.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.