Какая временная сложность у Binary Search?

Временная сложность бинарного поиска (Binary Search) — O(log n): на каждом шаге диапазон поиска уменьшается вдвое.

O(log n)

Бинарный поиск в отсортированном массиве делит диапазон пополам на каждом шаге, отбрасывая половину элементов. Число шагов — сколько раз n делится на 2 (log₂n):

function binarySearch(arr, target) {
  let left = 0, 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;
}

Наглядно

n = 1 000 000 → ~20 шагов (log₂ 1000000 ≈ 20)
n = 1 000 000 000 → ~30 шагов

Чрезвычайно эффективно на больших данных.

Пространственная сложность

• Итеративно — O(1) (несколько переменных).
• Рекурсивно — O(log n) (стек вызовов).

Условие

O(log n) достигается только на отсортированном массиве. Если не отсортирован — нужна сортировка O(n log n).

Бинарный против линейного поиска

• Линейный — O(n): проверяет каждый элемент.
• Бинарный — O(log n): в разы быстрее на больших данных.

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

Бинарный поиск — O(log n) по времени (диапазон делится пополам каждый шаг): для миллиона элементов ~20 шагов. Память O(1) итеративно, O(log n) рекурсивно. Требует отсортированного массива. Значительно быстрее линейного O(n).