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

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

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

Пример итеративного бинарного поиска для отсортированного массива чисел:

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

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

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

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

  return -1;
}

Здесь границы включительные. После проверки mid вы исключаете его из следующего диапазона, поэтому используете mid + 1 и mid - 1. Если написать left = mid, на маленьком диапазоне цикл может не сужаться.

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

На фронтенде это особенно заметно. Например, список товаров может отображаться в порядке, выбранном пользователем. Если вы ради поиска вызовете items.sort(), вы измените исходный массив. Это может внезапно поменять порядок в UI, сбить выбранный элемент и дать лишние рендеры. Безопаснее искать линейно в текущем порядке или подготовить отдельную копию: const sortedItems = [...items].sort(comparator).

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

Для первого вхождения нужно при совпадении сохранить текущий индекс и продолжить искать левее:

function findFirst(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;
  let result = -1;

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

    if (numbers[mid] >= target) {
      if (numbers[mid] === target) {
        result = mid;
      }
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return result;
}

Это полезный нюанс для интервью. Так вы показываете, что понимаете не только шаблон, но и контракт функции.

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

Хорошая формулировка на интервью может звучать так:

Бинарный поиск нужен, когда данные упорядочены. Я сравниваю цель с серединой диапазона и каждый раз отбрасываю половину, поэтому получаю O(log n). Но я обязательно проверяю, что порядок данных совпадает с comparator, а в коде аккуратно обновляю границы и отдельно решаю, что делать с отсутствием значения и дубликатами.

Такая фраза короткая, но закрывает принцип, сложность, условие применимости и риски реализации.