Що таке бінарний пошук?

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

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

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

Розгорнута відповідь

Коли застосовувати

Дані відсортовані (або об'єкт задачі задає монотонний предикат: при збільшенні індексу/параметра умова не переходить із true назад у false).
Є довільний доступ за індексом (масив/рядок/числовий діапазон). На зв'язних списках бінарний пошук неефективний.
Потрібен швидкий пошук/вставка позиції у великому відсортованому масиві.

Як це працює (ідея)

Обираємо межі діапазону: lo і hi.
Знаходимо середину mid = lo + floor((hi - lo) / 2).
Порівнюємо arr[mid] із ціллю і відкидаємо половину: або зсуваємо lo, або hi.
Повторюємо, поки діапазон не стане порожнім.

Складність

Час: O(log n).
Пам'ять: O(1) для ітеративної версії; O(log n) для рекурсивної через стек.

Базова реалізація (ітеративна, JS)

function binarySearch(arr, x) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    // Безпечна середина без переповнення і без 32-бітного зсуву
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === x) return mid;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1; // не знайдено
}

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

У JavaScript числа - 64-бітні з рухомою комою, тому класичного переповнення, як у Java/C++, немає. Але бітові зсуви приводять до 32-бітного цілого, що може бути небажаним на дуже великих індексах, тому використовуйте Math.floor((hi - lo) / 2).

Перша/остання позиція та індекс вставки

Часто потрібно знайти не «якийсь» індекс рівного елемента, а ліву/праву межу або позицію для вставки.

// lowerBound: перша позиція, де елемент >= x (ліва межа)
function lowerBound(arr, x) {
  let lo = 0, hi = arr.length; // напівінтервал [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// upperBound: перша позиція, де елемент > x (права межа + 1)
function upperBound(arr, x) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] <= x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// Діапазон усіх входжень x
function searchRange(arr, x) {
  const first = lowerBound(arr, x);
  const lastExclusive = upperBound(arr, x);
  return first === lastExclusive ? [-1, -1] : [first, lastExclusive - 1];
}

// Приклад
const b = [1, 2, 2, 2, 3, 5];
console.log(lowerBound(b, 2)); // 1
console.log(upperBound(b, 2)); // 4
console.log(searchRange(b, 2)); // [1, 3]
console.log(lowerBound(b, 4)); // 5 - індекс вставки для 4

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

Якщо є монотонний предикат pred(i), можна знайти мінімальне i, для якого pred(i) істинний. Це корисно для задач оптимізації за параметром.

function firstTrue(lo, hi, pred) {
  // Повертає мінімальне i з [lo, hi], де pred(i) === true,
  // або hi + 1, якщо істинних значень немає
  let ans = hi + 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (pred(mid)) {
      ans = mid;
      hi = mid - 1; // звужуємо праворуч до першого true
    } else {
      lo = mid + 1; // зсуваємо в бік true
    }
  }
  return ans;
}

// Приклад: мінімальне n, за якого n*n >= target
const target = 50;
const i = firstTrue(0, 100, (n) => n * n >= target);
console.log(i); // 8, оскільки 7*7=49 < 50, 8*8=64 >= 50

Інваріанти та часті помилки

Межі та напівінтервали: для пошуку індексу зручно використовувати [lo, hi] і умову циклу lo <= hi; для lower/upperBound - напівінтервал [lo, hi) і умову lo < hi.
Середина: обчислюйте mid як lo + floor((hi - lo) / 2), щоб уникати переповнень і зберігати прогрес.
Дублікати: базовий варіант повертає будь-який індекс збігу. Для першої/останньої позиції використовуйте lowerBound/upperBound.
Уникайте зациклення: після порівняння обов'язково виключайте mid із наступного діапазону (lo = mid + 1 або hi = mid - 1 для варіанта з [lo, hi]).
Узгодженість компаратора: порівнюйте так само, як масив було відсортовано (особливо для рядків з локалями та кастомних компараторів).
Не використовуйте на невідсортованих даних - отримаєте некоректний результат.

Коли краще не використовувати

Маленькі масиви, де лінійний пошук простіший і різниці за часом немає.
Відсутній довільний доступ (потік/ітератор/зв'язний список).
Пошук за ключем у невідсортованих структурах - використовуйте Map/Set. Бінарний пошук потрібен саме на відсортованих послідовностях.

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

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

Premium

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