Бинарный поиск

Цель: реализовать эффективный алгоритм поиска, который работает за логарифмическое время O(log n).

💡 Подсказка к решению

Основная идея бинарного поиска — на каждом шаге делить область поиска пополам.

Инициализация: Создайте два указателя: left (указывает на начало массива, индекс 0) и right (указывает на конец, arr.length - 1).
Цикл: Продолжайте поиск, пока left не станет больше right.
Поиск середины: На каждой итерации вычисляйте средний индекс: middle = Math.floor((left + right) / 2).
Сравнение:
- Если arr[middle] равен искомому элементу (target), вы нашли его! Возвращайте middle.
- Если arr[middle] меньше target, значит, искомый элемент может быть только в правой половине массива. Сдвиньте левую границу: left = middle + 1.
- Если arr[middle] больше target, искомый элемент — в левой половине. Сдвиньте правую границу: right = middle - 1.
Завершение: Если цикл закончился, а элемент не найден, верните -1.

👀 Решение

const binarySearch = (arr, target) => {
  // Инициализируем указатели на начало и конец массива.
  let left = 0;
  let right = arr.length - 1;
 
  // Продолжаем цикл, пока левый указатель не окажется правее правого.
  // Это условие означает, что область поиска еще не пуста.
  while (left <= right) {
    // Находим средний индекс.
    // Math.floor используется для округления вниз, чтобы получить целый индекс.
    const middle = Math.floor((left + right) / 2);
    const guess = arr[middle];
 
    // Сравниваем элемент в середине с искомым значением.
    if (guess === target) {
      // Элемент найден! Возвращаем его индекс.
      return middle;
    }
 
    // Если центральный элемент меньше искомого,
    // значит, target может находиться только в правой половине массива.
    if (guess < target) {
      // Сдвигаем левую границу поиска вправо от середины.
      left = middle + 1;
    } else {
      // В противном случае (центральный элемент больше искомого),
      // target может быть только в левой половине.
      // Сдвигаем правую границу поиска влево от середины.
      right = middle - 1;
    }
  }
 
  // Если цикл завершился, а элемент так и не был найден,
  // это означает, что его нет в массиве.
  return -1;
};

Анализ решения:

Сложность по времени: O(log n). На каждом шаге мы уменьшаем область поиска вдвое, что делает этот алгоритм чрезвычайно быстрым для больших массивов.
Сложность по памяти: O(1). Алгоритм использует только несколько переменных для хранения указателей, независимо от размера входного массива.
Ограничение: Главное требование — массив должен быть отсортирован. Если массив не отсортирован, бинарный поиск вернет некорректный результат или не найдет существующий элемент.

Описание задачи

Вам нужно реализовать функцию binarySearch, которая принимает отсортированный массив чисел arr и число target. Функция должна найти target в массиве и вернуть его индекс. Если элемент не найден, функция должна вернуть -1.

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

Примеры

// Находит элемент в середине
binarySearch([1, 2, 3, 4, 5, 6], 4); // 3
 
// Находит элемент в массиве с отрицательными числами
binarySearch([-1, 0, 3, 5, 9, 12], 9); // 4
 
// Элемент отсутствует
binarySearch([1, 2, 3, 4, 5], 7); // -1
 
// Пустой массив
binarySearch([], 5); // -1

Требования

Функция должна называться binarySearch.
Функция должна работать только с отсортированными массивами.
Если элемент не найден, возвращайте -1.
Решение должно иметь сложность O(log n).

Описание задачи

Примеры

Требования

Бинарный поиск

Описание задачи

Примеры

Требования

🧑‍💻 Это не баг! Это фича!