Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Яка складність бінарного пошуку?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

### Чому O(log n)

На кожному кроці бінарний пошук ділить поточний діапазон навпіл і відкидає одну з половин. Після 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) за пам'яттю (ітеративно/рекурсивно). Це досягається завдяки поетапному діленню діапазону пошуку навпіл.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати646 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.