Что такое бинарный поиск?

Бинарный поиск (binary search) — это алгоритм поиска элемента в отсортированном массиве за O(log n) путём деления диапазона поиска пополам на каждом шаге.

Как работает

1. Берём средний элемент диапазона.
2. Если он равен искомому — нашли.
3. Если искомый меньше — ищем в левой половине.
4. Если больше — в правой.
5. Повторяем, пока диапазон не пуст.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Главное условие

Массив должен быть отсортирован — иначе алгоритм не работает.

Сложность

• Время: O(log n) — на каждом шаге диапазон вдвое меньше.
• Память: O(1) итеративно, O(log n) рекурсивно (стек).

Для сравнения: линейный поиск — O(n). На 1 млн элементов бинарный поиск — ~20 шагов.

Применение

Поиск в отсортированных данных, поиск границ, Array.prototype (некоторые движки), базы данных (индексы).

Коротко для собеседования

Бинарный поиск ищет в отсортированном массиве за O(log n), деля диапазон пополам: сравнивает со средним и отбрасывает половину. Требует сортировки. Память O(1) итеративно. Намного быстрее линейного O(n) на больших данных.