Есть ли требования к массиву, передаваемому на вход в функцию бинарного поиска

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

На интервью можно ответить прямо. Массив должен быть отсортирован, а правило сортировки должно совпадать с правилом сравнения внутри поиска. Для обычных чисел это сортировка по числовому возрастанию или убыванию. Для объектов это сортировка по конкретному полю, например price, id или createdAt.

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

Второе требование, это доступ по индексу за O(1). В JavaScript-массиве это естественно. В связном списке или потоке данных такой доступ дорогой или невозможный, поэтому бинарный поиск теряет смысл.

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

В JavaScript важно не забыть comparator при сортировке чисел. Плохая подготовка данных может сломать бинарный поиск еще до запуска самого алгоритма.

Плохой пример:

const values = [1, 10, 2, 20];
values.sort();
// [1, 10, 2, 20], потому что сравнение идет как у строк

Здесь сломается не скорость, а корректность. Числовой поиск будет думать, что массив упорядочен как числа, хотя порядок лексикографический. В UI это может выглядеть как пропавший товар, неверная позиция в списке или пустой результат фильтра.

Безопаснее так:

const values = [1, 10, 2, 20].sort((a, b) => a - b);

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

binarySearch(values, 10);

Практический вывод простой. Если вы говорите на интервью, что массив должен быть отсортирован, добавьте по тому же comparator. Так вы покажете, что понимаете не только идею алгоритма, но и реальные ошибки в JavaScript.

Отдельный frontend-риск связан с тем, что Array.prototype.sort() мутирует массив. Если отсортировать массив из props или state прямо перед бинарным поиском, можно изменить порядок данных для других частей компонента. В результате список внезапно перерисуется иначе, выбранный индекс перестанет соответствовать прежнему элементу, а аналитика клика по позиции станет неверной.

Небезопасно:

function ProductList({ products, targetPrice }) {
  products.sort((a, b) => a.price - b.price);
  const index = binarySearchByPrice(products, targetPrice);
  return <ProductCard product={products[index]} />;
}

Безопаснее готовить отдельное представление и не делать лишнюю сортировку на каждый рендер:

function ProductList({ products, targetPrice }) {
  const sortedByPrice = useMemo(
    () => [...products].sort((a, b) => a.price - b.price),
    [products]
  );

  const index = binarySearchByPrice(sortedByPrice, targetPrice);
  return index === -1 ? null : <ProductCard product={sortedByPrice[index]} />;
}

Практический вывод. Требование к массиву включает не только порядок, но и способ подготовки этого порядка. Во frontend лучше не менять входные данные, явно указать ключ сортировки и обработать случай, когда элемент не найден.

Во frontend бинарный поиск редко пишут каждый день вручную, но идея встречается в списках, виртуализации, поиске позиции по времени, ценам, id или координатам. Там данные часто представлены объектами, поэтому вопрос про порядок особенно важен.

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

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

На интервью отвечайте не только фразой, что массив должен быть отсортирован. Лучше сказать полную мысль:

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

Затем можно добавить нюанс по задаче. Для чисел нужен числовой comparator, для объектов нужен ключ сортировки, для дубликатов нужна отдельная логика поиска границы. Такой ответ звучит сильнее, чем простое перечисление условий.