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

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

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

Математическое обоснование

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

Пример на JavaScript

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;
}

const sortedArray = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(sortedArray, 7)); // 3

В этом примере массив из 6 элементов. Максимальное количество итераций — log₂(6) ≈ 2.58, то есть не более 3 шагов. Если бы мы использовали линейный поиск, в худшем случае потребовалось бы 6 шагов.

Вывод

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