Какая алгоритмическая сложность у бинарного поиска

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

Поэтому число шагов растет медленно. Для 16 элементов в худшем случае нужно около 4 делений диапазона. Для 1 000 000 элементов нужно около 20 шагов. В этом смысл O(log n): при удвоении размера данных добавляется примерно один шаг.

Хороший короткий ответ может быть таким:

У бинарного поиска временная сложность O(log n), если массив отсортирован. На каждом шаге мы сравниваем target с элементом в середине и отбрасываем половину диапазона. Дополнительная память в итеративной реализации O(1). Если массив надо сначала сортировать, стоимость сортировки считается отдельно.

Так лучше, чем просто назвать O(log n). Вы показываете, что понимаете условие корректности и не забываете про реальную стоимость решения.

Базовая итеративная реализация выглядит так:

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

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

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

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

  return -1;
}

Важны две детали. Во-первых, массив должен быть отсортирован по тому же правилу, по которому вы сравниваете значения. Во-вторых, границы нужно сдвигать за mid, иначе на некоторых входах цикл может не закончиться.

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

В React не сортируйте массив из state или props на месте:

// Плохо: sort мутирует исходный массив
const sorted = items.sort((a, b) => a.price - b.price);

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

const sortedItems = useMemo(
  () => [...items].sort((a, b) => a.price - b.price),
  [items],
);

Это не отменяет стоимость сортировки, но убирает лишнюю работу на каждом рендере и не ломает исходный порядок данных в UI.

Во frontend-задачах бинарный поиск встречается не только в учебных примерах. Вы можете использовать его для поиска позиции в отсортированном списке дат, ближайшего breakpoint, виртуализации длинного списка или работы с заранее подготовленными справочниками.

Но если у вас короткий список в UI, который меняется после каждого ответа сервера, бинарный поиск может быть лишним усложнением. В таком случае лучше выбрать решение, которое проще поддерживать и которое не ломает данные.

Обычный бинарный поиск возвращает индекс найденного элемента, но при дубликатах это не обязательно первый или последний индекс. Если задача требует найти первую позицию, нужно продолжать поиск влево после совпадения.

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

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

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

  return left;
}

Такой вариант возвращает позицию первого элемента, который не меньше target. Это полезно, когда нужно найти место вставки или левую границу диапазона.

На интервью держите ответ в три шага. Сначала назовите сложность: O(log n). Затем объясните причину: каждый шаг делит диапазон пополам. После этого добавьте ограничения. Данные должны быть отсортированы, доступ к середине должен быть быстрым, а стоимость сортировки нужно считать отдельно.

Если хотите усилить ответ, сравните с линейным поиском. Для одного поиска по неотсортированным данным O(n) может быть разумнее. Для многих поисков по одному отсортированному массиву бинарный поиск обычно выигрывает.