1. Введение: Игра в «Загадай число»

Представьте, что мы решили сыграть в классическую игру. Я загадал целое число в диапазоне от 1 до 100, а ваша задача — его угадать. За каждый неправильный ответ я буду говорить, «больше» мое число или «меньше» вашего.

Стратегия №1: Идем по порядку

Вы можете начать с единицы и спрашивать последовательно: «Это 1?», «Это 2?», «Это 3?»...
Такой подход называется линейным поиском.

• Плюс: Вы точно найдете число.

• Минус: Если я загадал 99, вам понадобится 99 попыток. А если мы расширим диапазон до миллиона? В худшем случае вы будете спрашивать до самого вечера.

Стратегия №2: Рубим пополам

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

Тут возможны три варианта:

1. Я скажу «Угадал!» (Идеально, закончили за 1 шаг).

2. Я скажу «Мое число больше».

3. Я скажу «Мое число меньше».

Если я сказал «больше», вы мгновенно понимаете: числа от 1 до 50 можно даже не проверять. Одним вопросом вы отсекли ровно половину вариантов. Теперь ваш диапазон поиска — от 51 до 100. Следующим шагом вы снова разделите остаток пополам и назовете 75.

В чем суть?

Давайте сравним эффективность этих подходов на больших числах:

Чувствуете мощь? Чтобы найти нужный элемент среди 4 миллиардов записей, бинарному поиску понадобится всего 32 проверки, в то время как линейный поиск может затянуться на годы.

Этот алгоритм и называется бинарным поиском (от лат. binarius — двойной, состоящий из двух частей).

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

2. Математика «на пальцах»: Почему это быстро?

Когда программисты говорят о скорости алгоритмов, они используют понятие Big O Notation (нотация «О» большое). Для бинарного поиска это . Но что это значит для обычного человека?

Принцип деления пополам

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

Если в линейном поиске каждый шаг — это «минус 1 вариант», то в бинарном — это «делить на 2».

Давайте посчитаем для массива из 16 элементов:

1. Шаг 1: 16 → осталось 8 элементов.

2. Шаг 2: 8 → осталось 4 элемента.

3. Шаг 3: 4 → осталось 2 элемента.

4. Шаг 4: 2 → остался 1 (тот самый!).

Всего 4 шага.

логарифм

Число шагов — это и есть логарифм от количества элементов по основанию 2.

Математически это записывается так: .

Логарифм — это, по сути, вопрос: «Сколько раз мне нужно разделить число на 2, чтобы дойти до единицы?».

Сравнение скоростей

Чтобы осознать разницу между линейным поиском и бинарным , давайте представим, что одна проверка занимает 1 миллисекунду (0.001 секунды).

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

Главный вывод

Скорость бинарного поиска растет невероятно медленно при увеличении объема данных. Именно это делает его одним из самых эффективных инструментов в программировании. Если ваши данные отсортированы — глупо не воспользоваться бинарным поиском.

3. Пишем код: Первая реализация (Итеративный подход)

Чтобы алгоритм заработал, нам нужно два «указателя» (границы): left (левая) и right (правая). Мы будем сжимать пространство между ними до тех пор, пока не найдем число или пока границы не пересекутся.

Вот классическая реализация на Python:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        # Находим середину
        mid = (left + right) // 2
        
        # 1. Нашли!
        if arr[mid] == target:
            return mid 
        
        # 2. Если середина больше цели — ищем в левой половине
        if arr[mid] > target:
            right = mid - 1
        
        # 3. Если середина меньше цели — ищем в правой половине
        else:
            left = mid + 1
            
    return -1  # Число не найдено

Как это работает на практике?

Давайте визуализируем поиск в массиве [1, 3, 5, 7, 9, 11, 13].

Пример А: Ищем число 7 (идеальный случай)

Пример Б: Ищем число 3 (чуть сложнее)

Почему это важно для новичка?

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

На что обратить внимание:

1. while left <= right: Если написать просто <, алгоритм может «потерять» последний элемент, когда границы сойдутся в одной точке.

2. mid - 1 и mid + 1: Мы уже проверили элемент под индексом mid. Он нам не подошел. Если мы не вычтем/прибавим единицу, мы рискуем попасть в бесконечный цикл, когда left и right застынут на месте.

4. Где ошибаются новички?

Бинарный поиск считается одним из самых сложных «простых» алгоритмов. Существует легенда, что даже опытные разработчики в 90% случаев допускают ошибку при написании его с нуля.

Давайте разберем три главные ловушки.

1. Переполнение целого числа (The Overflow Bug)

В нашем коде мы писали: mid = (left + right) // 2.
На Python это будет работать всегда. Но если вы перейдете на C++, Java или C#, здесь притаился баг, который годами жил в стандартных библиотеках!

• Проблема: Если массив очень большой (например, 2 миллиарда элементов), то left + right может превысить максимальное значение типа int (2,147,483,647). Произойдет переполнение, число станет отрицательным, и программа «упадет».

• Как правильно:

  # Вместо (left + right) // 2
  mid = left + (right - left) // 2
  

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

2. Бесконечный цикл

Самая частая ошибка — забыть про + 1 или - 1 при обновлении границ.

• Ошибка: left = mid или right = mid.

• Почему это плохо: Представьте массив из двух элементов: [5, 10], и вы ищете 10.

  1. left = 0, right = 1. mid станет 0 (индекс числа 5).

  2. Число 5 меньше 10, поэтому срабатывает ветка left = mid.

  3. left снова равен 0.

  4. На следующей итерации mid снова станет 0.

  5. Поздравляем, вы зациклились!

Всегда исключайте mid из поиска, так как вы его уже проверили: left = mid + 1 или right = mid - 1.

3. Условие выхода (<= против <)

Часто возникает вопрос: писать while left <= right или while left < right?

• Правило большого пальца: Если вы ищете конкретное значение и используете mid + 1 / mid - 1, используйте <=.

• Если вы напишете <, то в ситуации, когда в массиве останется один-единственный элемент (и именно он будет искомым), цикл просто не выполнится, и вы получите -1 (не найдено).

4. Забытая сортировка

Это звучит банально, но бинарный поиск не работает на неотсортированных данных.
Если вы получили данные из API или базы данных, сначала убедитесь, что они упорядочены.

Совет: Если вам нужно найти элемент в массиве всего один раз, быстрее использовать обычный перебор . Сортировка сама по себе занимает больше времени (), чем бинарный поиск. Бинарный поиск выгоден только тогда, когда массив уже отсортирован или вам нужно искать в нем многократно.

5. Продвинутый уровень: Левая и правая границы

До этого момента мы рассматривали идеальный массив, где каждое число встречается один раз. Но что, если массив выглядит так: [1, 2, 2, 2, 3, 4]?

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

1. Индекс самой первой двойки?

2. Индекс самой последней двойки?

3. Количество двоек в массиве?

Обычный бинарный поиск тут бессилен — он «выплевывает» первый попавшийся подходящий индекс и завершается.

Как найти самую левую границу (First Occurrence)

Логика проста: если мы нашли искомое число, мы не останавливаемся. Мы запоминаем этот индекс, но продолжаем искать «левее», ведь там могут быть еще такие же числа.

def find_first(arr, target):
    left = 0
    right = len(arr) - 1
    result = -1 # Сюда будем сохранять последний найденный индекс

    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid     # Запомнили индекс!
            right = mid - 1  # Но продолжаем искать левее
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return result

Как найти самую правую границу (Last Occurrence)

Логика зеркальная: если нашли число — запоминаем индекс и продолжаем искать правее.

        if arr[mid] == target:
            result = mid     # Запомнили!
            left = mid + 1   # Ищем правее

Зачем это нужно в реальности?

1. Диапазоны: Если вы знаете индекс первой «двойки» (допустим, 1) и индекс последней (допустим, 3), вы легко вычислите их количество: 3 - 1 + 1 = 3.

2. Задачи «ближайший элемент»: С помощью модифицированного поиска границ можно найти, например, первое число в массиве, которое больше или равно X (это называется lower_bound).

3. SQL-запросы: Когда вы пишете WHERE price BETWEEN 100 AND 500 в базе данных, внутри часто отрабатывает именно поиск по границам в индексах.

Как запомнить разницу?

• Обычный поиск: Нашел? Сразу return mid.

• Поиск левой границы: Нашел? Запомнил и right = mid - 1 (сдвигаем правую границу к началу).

• Поиск правой границы: Нашел? Запомнил и left = mid + 1 (сдвигаем левую границу к концу).

Это маленькое изменение превращает простой алгоритм в мощный инструмент для работы с диапазонами данных.

6. Где это применяется в жизни?

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

1. Базы данных и индексы

Когда вы делаете запрос в базе данных (например, ищете пользователя по ID), она не перебирает миллионы строк по порядку. В базах существуют так называемые индексы (чаще всего это B-деревья). Поиск по индексу — это, по сути, продвинутый бинарный поиск. Без него поиск вашего профиля в соцсети занимал бы минуты, а не миллисекунды.

2. Git Bisect: Машина времени для багов

У разработчиков есть замечательный инструмент — git bisect. Представьте: у вас есть 1000 коммитов. Вчера всё работало, а сегодня — баг. Какой именно коммит всё сломал?
Вместо того чтобы проверять каждый коммит вручную, вы запускаете git bisect. Он:

1. Переходит на коммит №500.

2. Спрашивает вас: «Тут работает?».

3. Если вы говорите «Нет», он понимает, что ошибка в первой половине, и переходит на №250. Так он находит «виновный» коммит всего за 10 шагов.

3. Стандартные библиотеки языков

Даже если вы не пишете бинарный поиск сами, вы его используете:

• В Python есть модуль bisect.

• В C++ есть std::lower_bound и std::binary_search.

• В Java есть Arrays.binarySearch. Знание того, как они устроены, помогает понимать их ограничения (например, почему они требуют отсортированный массив).

4. Бинарный поиск «по ответу» (Optimization Problems)

Это настоящий «хакерский» прием в алгоритмах. Иногда у нас нет массива, но нам нужно найти число в диапазоне.

• Пример: Вы строите забор и хотите узнать максимальную длину секции, чтобы уложиться в бюджет.

• Вы не перебираете все длины (1см, 2см, 3см...).

• Вы пробуете среднее значение (например, 5 метров). Если денег хватает — пробуете больше (7.5 метров). Если нет — меньше. Это позволяет решать сложнейшие задачи оптимизации за доли секунды.

5. Словари и автодополнение

Когда вы начинаете вводить слово в поисковой строке, система ищет подходящие варианты в отсортированном словаре. Бинарный поиск позволяет мгновенно найти диапазон слов, начинающихся на «прогр...», среди сотен тысяч других.

7. Заключение

Бинарный поиск — это один из тех алгоритмов, который наглядно показывает разницу между «просто кодом» и эффективным решением. Мы прошли путь от простой детской игры с угадыванием чисел до нюансов реализации, которые могут поставить в тупик даже опытного разработчика.

Краткий чек-лист для самопроверки:

Если вы решили написать бинарный поиск с нуля, проверьте себя по этим пунктам:

1. Данные отсортированы? (Без этого алгоритм превращается в генератор случайных ошибок).

2. Условие цикла while left <= right? (Не теряете ли вы последний элемент?).

3. Вычисление mid защищено от переполнения? (left + (right - left) // 2).

4. Границы обновляются с шагом? (mid + 1 или mid - 1).

5. Нужны ли дубликаты? (Если да — используйте поиск левой или правой границы).

Что дальше?

Алгоритмы — это навык, который быстро «ржавеет» без практики. Чтобы закрепить материал, я рекомендую заглянуть на LeetCode и решить пару классических задач:

• Binary Search (база);

• First Bad Version (поиск границы);

• Search in Rotated Sorted Array (задачка со «звездочкой»).

Анонсы новых статей, полезные материалы, а так же если в процессе у вас возникнут сложности, обсудить их или задать вопрос по этой статье можно в моём Telegram-сообществе. Смело заходите, если что-то пойдет не так, — постараемся разобраться вместе.