Рекурсивная реализация: элегантность и цена

Рекурсия выражает бинарный поиск более декларативно: «Поиск в массиве — это поиск в середине, иначе поиск в подмассиве». Код становится лаконичнее, но мы платим за это вызовами функций и расходом стековой памяти.

public class BinarySearchRecursive {

    /**
     * Публичный метод-обертка, скрывающий детали рекурсивной реализации.
     * 
     * @param array отсортированный массив целых чисел
     * @param target искомое значение
     * @return индекс target или -1
     */
    public static int search(int[] array, int target) {
        if (array == null) {
            throw new IllegalArgumentException("Array cannot be null");
        }
        // Запускаем рекурсию с полным диапазоном
        return searchRecursive(array, target, 0, array.length - 1);
    }

    /**
     * Приватный рекурсивный вспомогательный метод.
     * 
     * @param array исходный массив (не меняется)
     * @param target искомое значение
     * @param left левая граница поиска (включительно)
     * @param right правая граница поиска (включительно)
     * @return индекс target или -1
     */
    private static int searchRecursive(int[] array, int target, int left, int right) {
        // Базовый случай: интервал поиска пуст
        // Это аналог выхода из цикла while (left <= right)
        if (left > right) {
            return -1;
        }

        // Вычисляем середину
        int mid = left + (right - left) / 2;
        int midValue = array[mid];

        // Базовый случай: нашли элемент
        if (midValue == target) {
            return mid;
        }

        // Рекурсивный шаг: выбираем половину и вызываем себя
        if (midValue < target) {
            // Искомое значение больше — ищем в правой половине
            return searchRecursive(array, target, mid + 1, right);
        } else {
            // Искомое значение меньше — ищем в левой половине
            return searchRecursive(array, target, left, mid - 1);
        }
    }
}

Анализ рекурсивной версии:
Чистота: Нет изменяемых переменных в цикле. Алгоритм читается как математическая рекуррентная формула.
Стоимость вызовов: Каждый рекурсивный шаг добавляет фрейм в стек вызовов. Фрейм содержит локальные переменные mid, midValue и параметры left, right. Глубина рекурсии составляет ⌈log₂n⌉ + 1 (включая первый вызов). На массиве из миллиона элементов глубина не превысит 20 уровней. Звучит безопасно, но...
Проблема переполнения стека: Стандартный размер стека в Java потоке — 1 МБ. 20 фреймов занимают крошечную часть. Однако в средах с ограниченным стеком (встроенные системы, агрессивные настройки JVM -Xss) или при поиске в коллекциях, эмулируемых через рекурсивные структуры, риск существует. Теоретически, на массиве размером 2³⁰ (~1 миллиард) элементов глубина достигла бы 31, что все еще безопасно, но практические ограничения JVM на размер массива не позволят такой эксперимент.
Оптимизация хвостовой рекурсии: Java не гарантирует оптимизацию хвостовой рекурсии (TCE), в отличие от языков функциональной парадигмы (Scala, Haskell). Каждый вызов будет реализован полностью. Поэтому итеративная версия всегда предпочтительнее с точки зрения производительности.


#Java #для_новичков #beginner #algorithm #sorted #binary

Асимптотический анализ: время и память

Временная сложность: O(log n)
Логарифмическая сложность означает, что с каждой итерацией мы отбрасываем половину оставшихся кандидатов. Формально: пусть T(n) — время поиска в массиве размера n. Тогда T(n) = T(n/2) + O(1), где O(1) — это сравнение и вычисление mid. Решая это рекуррентное соотношение по методу мастера, получаем T(n) = Θ(log n). В худшем случае нам потребуется ⌊log₂n⌋ + 1 сравнение.
Для системы масштабирования: увеличение коллекции в 1024 раз (2¹⁰) добавит только 10 итераций. Это волшебство логарифма: поиск в миллионе записей требует максимум 20 шагов, в миллиарде — 30.

Пространственная сложность:
Итеративная версия: O(1) дополнительной памяти. Используем фиксированный набор переменных (left, right, mid, midValue), не зависящий от размера входных данных. Масштабирование идеальное.
Рекурсивная версия: O(log n) из-за стековых фреймов. Каждый вызов создает фрейм (~24-32 байта на локальные переменные, указатель на return address и т.д.). При глубине log n общий объем стека линейно зависит от log n. На практике это означает: если ваша JVM позволяет глубину стека 1000 вызовов, вы безопасно ищете в массивах до 2¹⁰⁰⁰ элементов (число с 300 знаками), что в цифровом виде превышает количество атомов во Вселенной.


Границы применимости: когнитивный диссонанс производительности

Бинарный поиск — не серебряная пуля. Есть контексты, где он не только не выигрывает, но и проигрывает линейному поиску.

1. При малых n (n < 50-100)
Константы в алгоритмах имеют значение. Бинарный поиск требует деления, сложения, ветвления, что накладывает фиксированный налог в несколько процессорных циклов. Линейный поиск для n = 10 может выполниться за 10 простых сравнений, тогда как бинарный — за 4-5 сложных операций. Разница в наносекундах настолько мала, что не компенсирует накладные расходы на предварительную сортировку (если она не была сделана заранее).
Точка окупаемости зависит от архитектуры процессора, языка и стоимости операции сравнения. Для примитивов в Java порог может лежать в диапазоне 50-100 элементов. Для объектов, где сравнение требует дорогого Comparator или метода compareTo, порог смещается влево.

2. При динамических данных с частой вставкой
Если ваша библиотека пополняется новыми книгами каждые 10 минут, а поиск пользователей идет каждую секунду, поддержание отсортированности становится болью. Вставка в отсортированный массив стоит O(n) (сдвиг всех правых элементов). Для n = 10⁶ каждая вставка — это миллион операций копирования. Даже если вы используете сбалансированные структуры вроде TreeSet или PriorityQueue, где вставка O(log n), константы выше, чем в HashSet, и скорость поиска по индексу теряется.
В таких сценариях часто используют гибридный подход: данные хранятся в неотсортированном виде, периодически (например, раз в час) накопленное за период сортируется и сливается с основным отсортированным массивом методом сортировки слиянием. Или используются блочные структуры (bucketed arrays), где каждый блок отсортирован внутри, а новые элементы собираются в буфере.

3. Когда стоимость сравнения доминирует
В бинарном поиске мы всегда делаем log n сравнений. В линейном — в среднем n/2. Если n = 1000, бинарный поиск сделает ~10 сравнений, линейный — 500. Но что если каждое сравнение — это взятие блока данных с диска или сеть RPC? Тогда log n vs n/2 не имеет значения: оба варианта требуют одного дискового доступа (если данные кешированы), и разница в 490 сравнений — просто CPU-циклы в памяти. Бинарный поиск выигрывает в вычислительной сложности, но не в I/O.

4. Когда данные не помещаются в память, но отсортированы
Если массив лежит на диске и доступ к нему происходит через постраничную загрузку (paging), бинарный поиск становится врагом локальности. Итерация 0 читает страницу с середины. Итерация 1 читает страницу с четвертью или тремя четвертями — совершенно другая страница. Для дисковых массивов может быть выгоднее использовать B-деревья или интерполяционный поиск, учитывающий вероятность расположения данных на носителе.

#Java #для_новичков #beginner #algorithm #sorted #binary

Глава 4: Эффективный поиск. Бинарный и не только

Модификации и родственные методы

Ранее мы рассмотрели классический бинарный поиск, который эффективно отвечает на вопрос «есть ли элемент X в массиве?» и возвращает случайную позицию в случае дубликатов. Но реальные задачи редко сводятся к такому простому запросу. Что делать, если вам нужно найти все книги с заданным названием в каталоге, где дубликаты вполне закономерны (например, несколько экземпляров одного издания)? А как насчет поиска диапазона — всех книг, выпущенных между 2020 и 2023 годом включительно? Или если вы знаете, что данные распределены не просто монотонно, а равномерно, и хотите использовать это свойство для ускорения?
Эти вопросы приводят нас к модификациям классического алгоритма и его альтернативам. Каждая модификация сохраняет логарифмическую природу, но меняет инварианты и условия завершения.


Поиск границ в массиве с дубликатами

Проблема неоднозначности стандартной реализации

Представьте массив книг, отсортированных по названию:

String[] titles = {
    "Война и мир", "Война и мир", "Война и мир", 
    "Гарри Поттер", "Гарри Поттер", 
    "Мастер и Маргарита"
};

Вызываем Arrays.binarySearch(titles, "Война и мир"). Результат? Не определен. Javadoc гарантирует лишь, что будет возвращен какой-то индекс из диапазона дубликатов, если они существуют. Это недопустимо, когда вам нужен первый экземпляр для отображения в UI или последний для расчета границ диапазона.

Инвариант для поиска первого вхождения

Чтобы гарантированно найти самую левую позицию элемента, мы меняем логику завершения. Классический поиск завершается при точном совпадении array[mid] == target. Мы же должны продолжать поиск в левой половине даже после нахождения совпадения, потому что там может скрываться еще более ранний дубликат.

Новый инвариант: алгоритм поддерживает две зоны — переднюю, где все элементы строго меньше target, и заднюю, где элементы больше или равны target. Когда цикл завершается, указатель left будет указывать на первый элемент, равный target, или на позицию вставки, если target отсутствует.


#Java #для_новичков #beginner #algorithm #sorted #binary