Чому алгоритм називають «бінарним»?

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

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

Алгоритм називають «бінарним», тому що на кожному кроці він робить двійковий (із двох варіантів) вибір або ділить простір рішень на дві частини. Це спирається на двійкову логіку (0/1, істина/хиба) і часто призводить до логарифмічної за основою 2 складності, як у бінарному пошуку.

Детальна відповідь

Що означає «бінарний» в алгоритмах

«Бінарний» (від лат. bi - «два») - ключова дія алгоритму зводиться до вибору між двома альтернативами або до розбиття на дві підмножини.
Рішення приймається за двійковою логікою: так/ні, менше/більше, підходить/не підходить.
Часто такі алгоритми працюють за O(log2 n), тому що на кожному кроці «з'їдають» приблизно половину варіантів або один біт інформації.

Де це трапляється

Бінарний пошук: n → n/2 → n/4 → … - на кожному порівнянні обирається одна з двох половин відсортованого масиву.
Швидке піднесення до степеня (binary exponentiation): подання показника у двійковому вигляді; для кожного біта виконується «взяти/не взяти» множник.
Бінарні дерева та купи: у кожної вершини не більше двох нащадків; операції йдуть по одній із двох гілок.
Бінарне підняття (binary lifting): переходи за степенями двійки 2^k, рішення формуються з «бітів» довжини шляху.

Чому саме така назва

Два наслідки на крок: вибір лівої чи правої гілки/половини.
Ділення навпіл: зменшення задачі приблизно вдвічі на ітерацію.
Опора на двійкове подання: рішення/шляхи кодуються бітами, складність співвідноситься з кількістю бітів.

Приклад: бінарний пошук (JavaScript)

Класичний приклад «бінарності»: на кожному порівнянні ми обираємо одну з двох половин відсортованого масиву. Нижче - варіант lower_bound (перша позиція, де елемент не менший за target).

Підтримуємо інваріант напівінтервалу [l, r), де відповідь завжди перебуває всередині.
На кожній ітерації беремо середину m і вирішуємо: йти ліворуч чи праворуч.
Зупиняємось, коли l == r - це і є відповідь.

javascript

// Бінарний пошук: позиція першого елемента >= target (lower_bound)
function lowerBound(arr, target) {
  let l = 0, r = arr.length; // напівінтервал [l, r)
  while (l < r) {
    const m = l + ((r - l) >> 1); // середина без ризику переповнення
    if (arr[m] >= target) {
      r = m;          // шукане в лівій половині (включно з m)
    } else {
      l = m + 1;      // шукане в правій половині (строго після m)
    }
  }
  return l;           // індекс місця вставки/першого >= target
}

// Приклад
const a = [1, 3, 5, 7, 9];
console.log(lowerBound(a, 6)); // 3 (елемент 7)

Ключові властивості та вимоги «бінарних» підходів

Потрібна монотонність: предикат має бути істинним на одному кінці діапазону і хибним на іншому (або дані мають бути відсортовані).
Складність зазвичай O(log2 n) за кількістю кроків; пам'ять - O(1) в ітеративній формі.
Важливо коректно підтримувати інваріанти меж і обробляти дублікати/порожні масиви/вихід за діапазон.

Чим «бінарний» відрізняється від інших підходів

Тернарний пошук ділить діапазон на три частини; бінарний - на дві.
Інтерполяційний пошук обирає позицію за оцінкою, а не обов'язково середину; він не «бінарний».
«Бінарний» не означає обов'язково побітові операції - йдеться про двійковий вибір/двійкову структуру кроку.

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

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

Premium

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