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

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

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

public class BinarySearchBounds {

    /**
     * Поиск первого вхождения целевого значения.
     * Если элемент отсутствует, возвращает индекс, где он должен быть вставлен.
     * 
     * @return индекс первого вхождения target или potential insertion point
     */
    public static int findFirst(int[] array, int target) {
        if (array == null) throw new IllegalArgumentException("Array cannot be null");
        
        int left = 0;
        int right = array.length - 1;
        int result = -1; // Потенциальная позиция вставки
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = array[mid];
            
            if (midValue < target) {
                // Цель строго правее
                left = mid + 1;
            } else if (midValue > target) {
                // Цель строго левее
                right = mid - 1;
            } else {
                // Нашли совпадение, но продолжаем искать в левой половине
                result = mid; // Запомнили потенциальный ответ
                right = mid - 1; // Сдвинули границу влево
            }
        }
        
        // Если result остался -1, target не найден. Можно вернуть left как точку вставки.
        return result != -1 ? result : left;
    }
    
    /**
     * Поиск последнего вхождения целевого значения.
     */
    public static int findLast(int[] array, int target) {
        if (array == null) throw new IllegalArgumentException("Array cannot be null");
        
        int left = 0;
        int right = array.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = array[mid];
            
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                result = mid; // Запомнили потенциальный ответ
                left = mid + 1; // Ключевое отличие: сдвигаемся вправо
            }
        }
        
        return result != -1 ? result : left - 1; // left указывает после последнего <= target
    }
}

Ключевые отличия от классического поиска:
Сохранение состояния: Переменная result запоминает последнюю удачную позицию. Это нарушает чистоту инварианта, но необходимо для корректности.
Асимметричные действия: При нахождении target мы не выходим, а сдвигаем границу в сторону, противоположную от искомой границы. Для findFirst — влево, для findLast — вправо.
Выходное значение: В отсутствие элемента метод возвращает не -1, а точку вставки. Это делает API более универсальным для построения диапазонных запросов.
Поиск последнего вхождения: симметричная логика

Метод findLast зеркально отражает findFirst. Когда находится совпадение, мы продолжаем поиск в правой половине, потому что там может быть еще один дубликат. После завершения цикла left указывает на первый элемент строго больше target, поэтому left - 1 — это последний элемент, меньший или равный target.

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

Поиск диапазона

От границ к диапазону: композиция операций

Теперь, когда у нас есть инструменты для поиска границ, задача «найти все книги, изданные в 2020-2023 годах» решается композицией:

public class LibraryRangeSearch {

    static class Book implements Comparable<Book> {
        String title;
        int year;
        
        // Конструктор, геттеры...
        
        @Override
        public int compareTo(Book other) {
            return Integer.compare(this.year, other.year);
        }
    }
    
    /**
     * Поиск всех книг в заданном диапазоне лет [startYear, endYear].
     * Возвращает подмассив (views) для экономии памяти.
     */
    public static List<Book> findBooksByYearRange(Book[] library, int startYear, int endYear) {
        if (library == null || startYear > endYear) {
            return Collections.emptyList();
        }
        
        // Создаем фиктивные книги-границы для поиска
        Book startDummy = new Book("", startYear);
        Book endDummy = new Book("", endYear);
        
        // Находим первую книгу с year >= startYear
        int leftIndex = findFirstIndex(library, startDummy);
        
        // Находим последнюю книгу с year <= endYear
        int rightIndex = findLastIndex(library, endDummy);
        
        if (leftIndex == -1 || rightIndex == -1 || leftIndex > rightIndex) {
            return Collections.emptyList();
        }
        
        // Возвращаем view для избежания копирования
        return Arrays.asList(library).subList(leftIndex, rightIndex + 1);
    }
    
    // Адаптер для работы с Comparable объектами
    private static int findFirstIndex(Book[] array, Book target) {
        int left = 0, right = array.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = array[mid].compareTo(target);
            if (cmp < 0) left = mid + 1;
            else if (cmp > 0) right = mid - 1;
            else { result = mid; right = mid - 1; }
        }
        return result != -1 ? result : left;
    }
    
    private static int findLastIndex(Book[] array, Book target) {
        int left = 0, right = array.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = array[mid].compareTo(target);
            if (cmp < 0) left = mid + 1;
            else if (cmp > 0) right = mid - 1;
            else { result = mid; left = mid + 1; }
        }
        return result != -1 ? result : left - 1;
    }
}

Анализ производительности: Поиск диапазона требует двух бинарных поисков — O(log n) + O(log n) = O(log n). После этого мы получаем непосредственный доступ к результату за O(1). Если результатов много (k элементов), итоговая сложность O(log n + k). Это намного эффективнее линейного сканирования всей библиотеки O(n).

Важное замечание: Метод возвращает subList, который является view исходного массива. Изменения в исходном массиве отразятся в результате. Для защиты нужно скопировать: new ArrayList<>(Arrays.asList(...).subList(...)).


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

Альтернативный подход: поиск нижней границы + линейное сбирание

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

public static List<Book> findBooksByYearRangeOptimized(Book[] library, int startYear, int endYear) {
    int startIdx = findFirstIndex(library, new Book("", startYear));
    if (startIdx == -1 || startIdx >= library.length) return Collections.emptyList();
    
    List<Book> result = new ArrayList<>();
    for (int i = startIdx; i < library.length && library[i].year <= endYear; i++) {
        result.add(library[i]);
    }
    return result;
}

Этот подход имеет сложность O(log n + k) в худшем случае, но с меньшими константами, потому что второй бинарный поиск заменен на последовательное чтение (кэш-приятно).


Интерполяционный поиск — когда данные говорят сами за себя

Интуиция: зачем всегда делить пополам?

Представьте телефонный справочник, где фамилии распределены равномерно по алфавиту. Ищете «Иванов». Классический бинарный поиск откроет справочник ровно посередине — на букве «М», затем на «Г», затем на «Д»... Вместо этого можно интерполировать: поскольку «И» находится примерно на 10% алфавита, сразу открыть страницу на 10% от общего объема.

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

Математическая формула интерполяции

Если array[left] и array[right] известны, и target лежит между ними, то при равномерном распределении его позиция должна быть пропорциональна:

mid = left + (target - array[left]) * (right - left) / (array[right] - array[left])

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


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