Алгоритмы с нуля

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

Суть Бинарный поиск находит значение в отсортированном массиве за O(log n), раз за разом деля диапазон поиска пополам. Предусловие: массив должен быть отсортирован. Идея: держи границы [lo, hi], проверь средний элемент, отбрось половину, повтори.

◷ 18 min

У тебя есть отсортированный массив и тебе нужно найти значение. Линейный поиск идёт по массиву один элемент за раз: O(n). Для маленьких массивов нормально. Для больших — миллионы, миллиарды элементов — линейный поиск слишком медленный. Вот награда за сортировку: если массив отсортирован, ты можешь использовать бинарный поиск. Идея простая: проверь средний элемент. Если это твоя цель, готово. Если твоя цель меньше, отбрось правую половину и ищи в левой. Если твоя цель больше, отбрось левую половину и ищи в правой. На каждом шаге диапазон поиска уполовинивается. Через ~20 шагов массив из миллиона элементов сужается до одного. Это O(log n) — логарифм измеряет, сколько раз ты можешь разделить n пополам, пока ничего не останется.

Цель

После этого урока ты разбираешься в бинарном поиске: предусловие (массив должен быть отсортирован), алгоритм (держи границы, проверь середину, отбрось половину, повтори), почему это O(log n) (ты делишь диапазон поиска пополам примерно log n раз), опасности при реализации (условие цикла lo <= hi, вычисление mid без переполнения, правильное обновление границ чтобы избежать бесконечного цикла), и что возвращает бинарный поиск (индекс если найдено, или сигнал «не найдено»).

Идея

Предусловие: массив должен быть отсортирован

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

Пример: массив [1, 3, 5, 7, 9, 11]. Это отсортировано. Бинарный поиск будет работать правильно.

Массив [3, 1, 7, 5, 11, 9]. Это не отсортировано. Бинарный поиск сломается.

Идея: держи границы и дели пополам

Бинарный поиск держит две границы: lo (самый нижний индекс, ещё в игре) и hi (самый верхний индекс, ещё в игре). Диапазон поиска это [lo, hi] — все элементы от индекса lo до индекса hi включительно.

На каждом шаге:

Вычисли середину индекса: mid = Math.floor((lo + hi) / 2).
Проверь, равен ли arr[mid] цели. Если да, верни mid.
Если arr[mid] меньше цели, цель в правой половине. Отбрось левую половину: установи lo = mid + 1.
Если arr[mid] больше цели, цель в левой половине. Отбрось правую половину: установи hi = mid - 1.
Повтори, пока не выполнится lo > hi (диапазон пустой; цель не найдена).

Почему O(log n)?

На каждом шаге диапазон поиска сжимается вдвое. Сколько раз ты можешь разделить n пополам?

Из курса математики Логарифмы

Начиная с n элементов:

После шага 1: примерно n/2 элементов осталось.
После шага 2: примерно n/4 элементов осталось.
После шага 3: примерно n/8 элементов осталось.
…
После шага log₂(n): примерно 1 элемент (или 0, значит не найдено).

Так что максимум итераций это log₂(n). Для n = 1 000 000 это log₂(1 000 000) ≈ 20 шагов. Сравни с линейным поиском: 500 000 шагов в среднем.

Условие цикла: lo <= hi

Цикл продолжается, пока диапазон поиска не пустой: lo <= hi. Когда lo > hi, диапазон пустой, и цели нет в массиве.

Опасность 1: условие цикла

Частая ошибка — использовать lo < hi вместо lo <= hi. Если ты это сделаешь, ты упустишь случай lo == hi (один элемент осталось). Используй lo <= hi, чтобы проверить этот элемент.

Опасность 2: вычисление mid

Вычисление mid = (lo + hi) / 2 может переполниться в языках с фиксированной длиной целых чисел (Java, C++). Если lo и hi очень большие, lo + hi может превысить максимальное значение целого.

Безопасная формула: mid = lo + Math.floor((hi - lo) / 2). Или эквивалентно: mid = lo + ((hi - lo) >> 1) (сдвиг вправо на 1 это целочисленное деление на 2).

JavaScript не имеет этой проблемы с переполнением, но хорошо практиковать.

Опасность 3: обновление границ

После решения отбросить одну половину, ты должен обновить границу правильно:

Если цель в правой половине, установи lo = mid + 1 (не lo = mid). Если ты установишь lo = mid и arr[mid] не цель, ты будешь цикл в бесконечности, всегда проверяя тот же mid.
Если цель в левой половине, установи hi = mid - 1 (не hi = mid). Та же причина.

Что возвращает бинарный поиск?

Если цель найдена, верни её индекс. Если не найдена, верни -1 (или null, или выброси ошибку — в зависимости от твоего дизайна).

Код

Давай напишем бинарный поиск с нуля.

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

  while (lo <= hi) {
    // Вычисли mid безопасно
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === target) {
      return mid;  // Найдено!
    } else if (arr[mid] < target) {
      // Цель в правой половине
      lo = mid + 1;
    } else {
      // Цель в левой половине
      hi = mid - 1;
    }
  }

  // Цикл вышел: lo > hi. Цель не найдена.
  return -1;
}

Ключевые моменты:

lo и hi — это включительные границы (обе точки части диапазона поиска).
mid = lo + Math.floor((hi - lo) / 2) избегает переполнения и округляет вниз.
lo = mid + 1 и hi = mid - 1 гарантируют, что диапазон всегда сжимается (нет бесконечных циклов).
Цикл продолжается, пока lo <= hi.

Давай тестировать:

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

while (lo <= hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    lo = mid + 1;
  } else {
    hi = mid - 1;
  }
}
return -1;
}

// Тест 1: цель существует
const arr1 = [1, 3, 5, 7, 9, 11, 13];
console.log("Массив:", arr1);
console.log("Поиск 7:", binarySearch(arr1, 7), "(ожидаем 3)");
console.log("Поиск 1:", binarySearch(arr1, 1), "(ожидаем 0)");
console.log("Поиск 13:", binarySearch(arr1, 13), "(ожидаем 6)");

// Тест 2: цель не существует
console.log("Поиск 6:", binarySearch(arr1, 6), "(ожидаем -1)");
console.log("Поиск 0:", binarySearch(arr1, 0), "(ожидаем -1)");
console.log("Поиск 20:", binarySearch(arr1, 20), "(ожидаем -1)");

// Тест 3: граничный случай — один элемент
const arr2 = [42];
console.log("Один элемент [42], поиск 42:", binarySearch(arr2, 42), "(ожидаем 0)");
console.log("Один элемент [42], поиск 10:", binarySearch(arr2, 10), "(ожидаем -1)");

// Тест 4: больший массив
const arr3 = Array.from({length: 100}, (_, i) => i * 2);  // [0, 2, 4, ..., 198]
console.log("Большой массив (100 элементов), поиск 50:", binarySearch(arr3, 50), "(ожидаем 25)");
console.log("Большой массив, поиск 51:", binarySearch(arr3, 51), "(ожидаем -1)");

Вывод

Пошаговый разбор

Давай трассируем бинарный поиск на массиве [1, 3, 5, 7, 9, 11], ищем target = 7.


      1
      while (lo <= hi) {
    

      2
        const mid = lo + Math.floor((hi - lo) / 2);
    

      3
        if (arr[mid] === target) return mid;
    

      4
        else if (arr[mid] < target) lo = mid + 1;
    

      5
        else hi = mid - 1;
    

      6
      }

Разборка:

Шаг 1: Диапазон поиска [0, 5]. Проверь индекс 2 (значение 5). Слишком мало; ищи правую половину [3, 5].
Шаг 2: Диапазон поиска [3, 5]. Проверь индекс 4 (значение 9). Слишком много; ищи левую половину [3, 3].
Шаг 3: Диапазон поиска [3, 3]. Проверь индекс 3 (значение 7). Найдено! Верни 3.

Всего шагов: 3. Для не отсортированного массива из 6 элементов линейный поиск сканировал бы все 6. Бинарный поиск сканировал 3.

Сложность

Аспект	Значение
Время (лучший случай)	O(1) — цель это средний элемент на первой проверке
Время (средний случай)	O(log n)
Время (худший случай)	O(log n) — цель на краю, или не найдена
Память	O(1) — только две границы и индекс mid

Почему O(log n)?

Каждая итерация делит диапазон поиска пополам. Диапазон начинается с n элементов и сжимается: n → n/2 → n/4 → … → 1. Количество делений на две части это log₂(n).

Для разных размеров массива:

n	log₂(n)
100	примерно 7 шагов
1 000	примерно 10 шагов
1 000 000	примерно 20 шагов
1 000 000 000	примерно 30 шагов

Линейный поиск на 1 миллиарде элементов: 500 миллионов сравнений. Бинарный поиск: 30 сравнений. Ускорение астрономическое.

Предусловие: массив должен быть отсортирован

Если массив не отсортирован, бинарный поиск даст неправильные ответы. Сортировка стоит O(n log n) один раз. Потом каждый поиск O(log n). Это амортизирует стоимость сортировки на много поисков.

Если ты ищешь только раз, O(n log n) сортировка + O(log n) поиск = O(n log n) всего. Линейный поиск это O(n). Для одного поиска линейный лучше. Но для многих поисков бинарный выигрывает.

Память: O(1)

Бинарный поиск использует только постоянное количество дополнительной памяти: две границы (lo, hi) и один индекс (mid). Рекурсивные реализации добавляют O(log n) на стеке вызовов (глубина рекурсии это log n), но итеративная версия (показана здесь) это O(1).

Практика 0 / 5

Почему бинарный поиск требует отсортированный массив?

Сколько сравнений нужно бинарному поиску в худшем случае для поиска в массиве из 1 000 элементов?

Что возвращает бинарный поиск, если цели нет в массиве?

Почему `mid = lo + Math.floor((hi - lo) / 2)` безопаснее чем `mid = (lo + hi) / 2`?

Когда ты видишь что arr[mid] < target, почему ты устанавливаешь `lo = mid + 1` вместо `lo = mid`?

Частая ошибка

Ошибка на единицу / бесконечный цикл. Самая частая ошибка это установить lo = mid или hi = mid вместо lo = mid + 1 или hi = mid - 1. Если arr[mid] не цель, и ты установишь lo = mid, цикл будет пересчитывать arr[mid] навечно, создавая бесконечный цикл. Всегда используй mid + 1 и mid - 1 чтобы сжать диапазон.

lesson.inset.edge-case

Граничные случаи. Тестируй твой бинарный поиск на маленьких массивах: один элемент, два элемента, пустой массив (если применимо). Тестируй когда цель первый элемент, последний элемент, и полностью пропущена. Эти граничные случаи часто раскрывают ошибки в условии цикла.

Проверь себя

Викторина

У тебя есть отсортированный массив из 10 миллионов элементов и надо узнать есть ли там цель. Быстрее ли бинарный поиск чем линейный? Во сколько раз?

Итог

Бинарный поиск находит значение в отсортированном массиве раз за разом деля диапазон поиска пополам.

Предусловие: Массив должен быть отсортирован.

Алгоритм: Держи границы lo и hi. Проверь средний элемент arr[mid]. Если это цель, верни её индекс. Иначе, отбрось половину диапазона (левую или правую), и повтори. Когда lo > hi, диапазон пустой; верни «не найдено».

Сложность времени: O(log n) потому что ты делишь пополам диапазон поиска примерно log n раз. На 1 миллиард элементов примерно 30 шагов. Намного быстрее чем линейный поиск (500 миллионов шагов).

Сложность памяти: O(1) для итеративной версии (две границы и индекс).

Опасности:

Используй lo <= hi чтобы включить случай lo == hi (последний один элемент).
Используй lo + Math.floor((hi - lo) / 2) чтобы избежать переполнения.
Используй lo = mid + 1 и hi = mid - 1 чтобы гарантировать что диапазон сжимается на каждой итерации (избегай бесконечных циклов).

Когда использовать: После сортировки, для быстрых повторяющихся поисков на больших данных.

Почему это учить? Бинарный поиск один из самых важных алгоритмов в информатике. Он учит тебя как эксплуатировать отсортированный порядок для скорости, и показывает что O(log n) достижимо на практике.

Продолжить восхождение ↑Бинарный поиск по ответу