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

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

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

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

Детально

Ідея алгоритму

Бінарний пошук на кожному кроці порівнює цільовий елемент із серединою відсортованого діапазону і відкидає половину варіантів, продовжуючи в тій половині, що залишилась.

Асимптотика за часом

Найгірший і середній випадок: O(log n). Кількість порівнянь не перевищує ⌊log2(n)⌋ + 1.
Найкращий випадок: O(1), якщо шуканий елемент опинився одразу в середині.

Після кожного порівняння діапазон пошуку ділиться навпіл. Розмір діапазону, що залишається, - n, n/2, n/4, ..., 1. Кількість кроків k така, що n / 2^k ≤ 1, тобто k ≥ log2(n). Отже, кількість ітерацій пропорційна log2(n).

Просторова складність

Ітеративно: O(1) - використовується фіксована кількість вказівників/індексів.
Рекурсивно: O(log n) - глибина рекурсії дорівнює кількості ділень навпіл.

Вимоги та обмеження

Дані мають бути відсортовані за тим самим критерієм, за яким ви порівнюєте елементи.
Потрібен довільний доступ до елементів за O(1). У зв'язних списках бінарний пошук втрачає сенс і перетворюється на O(n).
Стабільність порядку і функція порівняння мають бути транзитивними (монотонність ключів).

Скільки це в кроках

n = 16: 16 → 8 → 4 → 2 → 1 - 5 порівнянь (≈ log2(16) + 1).
n = 1 000 000: близько 20 порівнянь.

Підводні камені

Переповнення при обчисленні середини: використовуйте mid = left + ((right - left) >> 1), а не (left + right) / 2.
Межі циклу: для діапазону [left, right] умова left ≤ right; для напівінтервалу [left, right) - left < right.
Дублікати: простий бінарний пошук повертає будь-який індекс; для першого/останнього входження використовуйте варіанти lower_bound/upper_bound.

Приклади коду

Ітеративний бінарний пошук (JS)

javascript

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1); // безпечніше, ніж (left + right) >> 1
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // не знайдено
}

// Приклад
const a = [1, 3, 4, 7, 9, 12, 18];
console.log(binarySearch(a, 9));  // 4
console.log(binarySearch(a, 2));  // -1

Перше входження (lower_bound)

javascript

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; // перший індекс, де arr[i] >= target
}

// Використання для "першого рівного"
const b = [1, 3, 3, 3, 5, 8];
const idx = lowerBound(b, 3);
const exists = idx < b.length && b[idx] === 3; // true
console.log(idx, exists); // 1 true

Бінарний пошук за відповіддю (монотонний предикат)

Техніка, коли шукане значення - мінімальне/максимальне, що задовольняє монотонну умову. Складність також O(log R) за діапазоном R можливих відповідей.

javascript

// Приклад: мінімальна вантажопідйомність, щоб перевезти weights за days (класична задача)
function minCapacity(weights, days) {
  let left = Math.max(...weights);
  let right = weights.reduce((s, x) => s + x, 0);
  const can = cap => {
    let need = 1, sum = 0;
    for (const w of weights) {
      if (sum + w > cap) { need++; sum = 0; }
      sum += w;
    }
    return need <= days;
  };
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (can(mid)) right = mid; else left = mid + 1;
  }
  return left;
}

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

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

Premium

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