Почему сложность бинарного поиска равна O(log n)?

Почему сложность бинарного поиска равна O(log n)?

Бинарный поиск — это алгоритм, который находит элемент в отсортированном массиве, последовательно сужая область поиска. На каждом шаге он сравнивает искомое значение со средним элементом и отбрасывает половину массива, где элемент точно не может находиться.

Как это связано с логарифмом?

Если массив имеет размер n, то после первого шага остаётся n/2 элементов, после второго — n/4, и так далее. Процесс продолжается, пока не останется один элемент. Количество шагов k удовлетворяет уравнению: n / 2^k = 1, откуда 2^k = n, то есть k = log₂(n). Таким образом, время выполнения растёт логарифмически относительно размера входных данных.

Пример на JavaScript

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;
}
// Для массива из 16 элементов нужно не более 4 шагов (log2(16)=4)

Где применяется?

Бинарный поиск используется в базах данных (B-деревья), поиске в отсортированных списках, отладке (git bisect) и многих других задачах, где данные упорядочены.

Вывод: O(log n) — это очень эффективная сложность, позволяющая обрабатывать большие объёмы данных за минимальное время. Бинарный поиск стоит применять везде, где данные отсортированы и требуется быстрый поиск.