Binary Search (Бинарный поиск)

Binary search — алгоритм поиска в отсортированном массиве, который на каждом шаге отбрасывает половину оставшихся элементов, достигая сложности O(log n).

Зачем нужно

Binary search превращает поиск из задачи на миллион операций в задачу на 20 операций. Для 1 000 000 элементов: линейный поиск — до 1 000 000 сравнений, бинарный — максимум 20 (log2(1 000 000) ~ 20).

Где используется

  • Поиск в отсортированных массивах и базах данных
  • Поиск границ (первый/последний элемент, удовлетворяющий условию)
  • Автодополнение и поиск по словарю
  • Оптимизационные задачи (binary search on answer)
  • Git bisect — поиск коммита с багом

Предпосылки

Обязательное условие

Массив должен быть отсортирован! Бинарный поиск не работает на неотсортированных данных.

Алгоритм

1. Установить left = 0, right = длина - 1
2. Пока left <= right:
   a. mid = (left + right) / 2 (целая часть)
   b. Если array[mid] === target → нашли, вернуть mid
   c. Если array[mid] < target → искать в правой половине (left = mid + 1)
   d. Если array[mid] > target → искать в левой половине (right = mid - 1)
3. Если вышли из цикла → элемент не найден

Визуализация

Ищем 7 в массиве [1, 3, 5, 7, 9, 11, 13]

Шаг 1: left=0, right=6, mid=3 → arr[3]=7 === 7 ✓ Найден!

Ищем 11:
Шаг 1: left=0, right=6, mid=3 → arr[3]=7  < 11 → left=4
Шаг 2: left=4, right=6, mid=5 → arr[5]=11 === 11 ✓ Найден!

Ищем 4:
Шаг 1: left=0, right=6, mid=3 → arr[3]=7  > 4 → right=2
Шаг 2: left=0, right=2, mid=1 → arr[1]=3  < 4 → left=2
Шаг 3: left=2, right=2, mid=2 → arr[2]=5  > 4 → right=1
left > right → не найден!

Реализация в JavaScript

Итеративная (рекомендуется)

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sorted[mid] === target) {
      return mid;
    }

    if (sorted[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

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

// Примеры
const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(arr, 23));  // 5
console.log(binarySearch(arr, 10));  // -1

Рекурсивная

function binarySearchRecursive(sorted, target, left = 0, right = sorted.length - 1) {
  if (left > right) return -1;

  const mid = Math.floor((left + right) / 2);

  if (sorted[mid] === target) return mid;

  if (sorted[mid] < target) {
    return binarySearchRecursive(sorted, target, mid + 1, right);
  }
  return binarySearchRecursive(sorted, target, left, mid - 1);
}

Поиск позиции для вставки (lower bound)

function lowerBound(sorted, target) {
  let left = 0;
  let right = sorted.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left; // индекс, куда вставить target, сохраняя порядок
}

const arr = [1, 3, 5, 7, 9];
console.log(lowerBound(arr, 6));  // 3 (вставить между 5 и 7)
console.log(lowerBound(arr, 5));  // 2 (позиция существующего 5)

Поиск первого и последнего вхождения

function findFirst(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) {
      result = mid;
      right = mid - 1; // продолжаем искать левее
    } else if (sorted[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

function findLast(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === target) {
      result = mid;
      left = mid + 1; // продолжаем искать правее
    } else if (sorted[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

const arr = [1, 2, 2, 2, 3, 4, 5];
console.log(findFirst(arr, 2)); // 1
console.log(findLast(arr, 2));  // 3

Сложность

Случай Время Память (итеративный) Память (рекурсивный)
Лучший O(1) — mid === target O(1) O(1)
Средний O(log n) O(1) O(log n) — стек
Худший O(log n) O(1) O(log n) — стек

Практические применения

// 1. Поиск в словаре (автодополнение)
function autocomplete(dictionary, prefix) {
  const start = lowerBound(dictionary, prefix);
  const results = ;

  for (let i = start; i < dictionary.length; i++) {
    if (!dictionary[i].startsWith(prefix)) break;
    results.push(dictionary[i]);
  }

  return results;
}

const words = ['apple', 'application', 'apply', 'banana', 'band'];
console.log(autocomplete(words, 'app')); // ['apple', 'application', 'apply']

// 2. Поиск в диапазоне дат
function findEventsInRange(sortedEvents, startDate, endDate) {
  const startIdx = lowerBound(
    sortedEvents.map(e => e.date),
    startDate
  );

  const results = ;
  for (let i = startIdx; i < sortedEvents.length; i++) {
    if (sortedEvents[i].date > endDate) break;
    results.push(sortedEvents[i]);
  }

  return results;
}

Частые ошибки

  1. Применять к неотсортированному массиву. Результат будет неопределённым
  2. Ошибка off-by-one. left <= right (не <) и mid + 1 / mid - 1 (не mid)
  3. Integer overflow при вычислении mid. В JS нет проблемы, но в C/Java: mid = left + (right - left) / 2
  4. Забывать обработать пустой массив. Цикл не выполнится, вернётся -1

Практика

  1. Реализуйте binarySearch без подглядывания в примеры
  2. Реализуйте функцию countOccurrences(sorted, target) используя findFirst и findLast
  3. Задача: найти квадратный корень числа с точностью 0.001 используя бинарный поиск по ответу
function sqrt(n, precision = 0.001) {
  let left = 0;
  let right = n;

  while (right - left > precision) {
    const mid = (left + right) / 2;
    if (mid * mid < n) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return (left + right) / 2;
}

console.log(sqrt(25));  // ~5.0
console.log(sqrt(2));   // ~1.414

Связанные темы

Ресурсы

  • Grokking Algorithms, глава 1 (Aditya Bhargava)
  • visualgo.net/en/bst — визуализация
  • LeetCode: Binary Search (задача #704) — практика