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

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

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

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

Контент

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

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

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

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

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

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

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

## Детально

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

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

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

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

### Чому саме O(log n)

Після кожного порівняння діапазон пошуку ділиться навпіл. Розмір діапазону, що залишається, - 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).
- Стабільність порядку і функція порівняння мають бути транзитивними (монотонність ключів).

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

1. n = 16: 16 → 8 → 4 → 2 → 1 - 5 порівнянь (≈ log2(16) + 1).
2. 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;
}
```

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

Для рев’юера

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

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