Чому бінарний пошук вимагає відсортованого масиву?

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

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

Бінарний пошук вимагає відсортованого масиву, тому що рішення «йти ліворуч чи праворуч» після порівняння із серединою коректно ділить масив на дві частини лише за глобального порядку елементів. При впорядкуванні одна половина гарантовано не містить шуканого значення, і її можна відкинути. У невідсортованому масиві такої гарантії немає, і алгоритм може відкинути частину з відповіддю.

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

Навіщо потрібен порядок

Ідея половинного ділення: ми беремо середину, порівнюємо із шуканим x і вирішуємо, в якій половині продовжити. Це рішення спирається на те, що всі елементи ліворуч не більші за середину (або не менші - залежно від порядку), а праворуч - навпаки.
Інваріант коректності: на кожному кроці множина кандидатів залишається інтервалом індексів, усередині якого елементи впорядковані. Порівняння із серединою гарантує, що одна з половин не може містити відповідь, і її безпечно відкинути.
Монотонність предиката: класичний двійковий пошук еквівалентний пошуку межі монотонного предиката P(i). Наприклад, P(i) := a[i] ≥ x на зростаючому масиві монотонний за i. На невідсортованому масиві P(i) стрибає (не монотонний), і межу коректно знайти не можна.
Не лише швидкість, а й коректність: без порядку алгоритм не просто стає повільнішим - він може повернути неправильну відповідь (або «не знайдено», хоча елемент є).

Ключовий інваріант: якщо масив відсортований за компаратором cmp, то для будь-якого mid вірно: усі i < mid - не більші за a[mid] (у порядку cmp), а всі i > mid - не менші за a[mid]. Саме це дозволяє відкидати половину.

Як працює бінарний пошук (коротко за кроками)

Підтримуємо межі [l, r] шуканого індексу.
Беремо mid = ⌊(l + r) / 2⌋.
Порівнюємо a[mid] з x.
Якщо a[mid] < x (за зростання), відповідь не може бути ліворуч, зсуваємо l = mid + 1; інакше r = mid - 1.
Повторюємо, поки інтервал не звузиться до порожнього або поки не знайдемо елемент.

Простий приклад коду (JS)

function binarySearch(arr, x) {
  // Потрібно: arr відсортований за зростанням
  let l = 0;
  let r = arr.length - 1;
  while (l <= r) {
    const mid = l + ((r - l) >> 1); // уникаємо переповнення
    if (arr[mid] === x) return mid;
    if (arr[mid] < x) l = mid + 1;
    else r = mid - 1;
  }
  return -1; // не знайдено
}

console.log(binarySearch([1, 3, 4, 7, 9, 12], 7)); // 3
console.log(binarySearch([1, 3, 4, 7, 9, 12], 8)); // -1

Що зламається на невідсортованому масиві

На невідсортованих даних рішення «куди йти» може відкинути потрібну половину:

const arr = [2, 9, 4, 7, 5];
const x = 5;
// l=0, r=4, mid=2 -> arr[2]=4. x>4 => йдемо праворуч (l=3)
// l=3, r=4, mid=3 -> arr[3]=7. x<7 => йдемо ліворуч (r=2)
// Тепер l=3, r=2 => цикл завершується, повертаємо -1, хоча 5 є (index=4)
// Помилка через відсутність глобального порядку: порівняння із серединою не гарантує, що ліворуч/праворуч немає відповіді.

Дублікати, компаратор і вимоги до порядку

Дублікати допускаються. Потрібно визначити мету: будь-який індекс елемента, перший (lower_bound) чи останній (upper_bound).
Порядок має бути тотальним і транзитивним за одним і тим самим компаратором, яким масив відсортовано і за яким виконуються порівняння в пошуку. Неузгоджений компаратор порушить інваріанти.
Особливі значення (наприклад, NaN) порушують порівнюваність: їх потрібно обробляти окремо або виключати.

Узагальнення через монотонний предикат (lower_bound)

Бінарний пошук насправді шукає межу, де предикат P(i) змінюється з false на true. У відсортованому за зростанням масиві предикат P(i): a[i] ≥ x монотонний, тому можна знайти перший індекс, де елемент не менший за x (lower_bound).

function lowerBound(arr, x) {
  // Повертає мінімальний індекс i, такий що arr[i] >= x.
  // Якщо такого немає - повертає arr.length.
  let l = 0, r = arr.length; // напівінтервал [l, r)
  while (l < r) {
    const mid = l + ((r - l) >> 1);
    if (arr[mid] >= x) r = mid; // true-зона
    else l = mid + 1;           // false-зона
  }
  return l;
}

const a = [1, 3, 3, 5, 8];
console.log(lowerBound(a, 3)); // 1 (перший індекс з 3)
console.log(lowerBound(a, 4)); // 3 (перший індекс з >=4 - це 5)
console.log(lowerBound(a, 9)); // 5 (немає таких елементів)

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

Якщо потрібен один пошук по невідсортованих даних, використовуйте лінійний прохід O(n).
Якщо пошуків багато, вигідно відсортувати один раз за O(n log n) і потім виконувати O(log n) на кожен запит.
Для динамічних даних підтримуйте структуру з порядком (наприклад, відсортований масив із бінарним пошуком і вставками через бінарний пошук + сплайс; або дерево/індекс), щоб зберігалася монотонність, необхідна двійковому пошуку.
Бінарний пошук застосовний не лише до масивів: він працює на будь-якій впорядкованій області значень/відповідей, де є монотонний критерій досяжності/виконуваності.

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

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

Premium

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