Итеративная реализация: фундамент

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

public class BinarySearch {

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

        // Пока интервал не схлопнулся (не стал пустым)
        while (left <= right) {
            // Вычисляем середину, защищаясь от переполнения
            // Эквивалентно (left + right) / 2, но без риска overflow
            int mid = left + (right - left) / 2;
            
            // Получаем значение по среднему индексу
            int midValue = array[mid];

            // Сравниваем с целевым
            if (midValue == target) {
                // Нашли! Возвращаем позицию.
                return mid;
            } else if (midValue < target) {
                // Искомое значение больше, чем midValue.
                // Отбрасываем левую половину, включая mid.
                // Новый поиск в (mid + 1, right).
                left = mid + 1;
            } else { // midValue > target
                // Искомое значение меньше, чем midValue.
                // Отбрасываем правую половину, включая mid.
                // Новый поиск в (left, mid - 1).
                right = mid - 1;
            }
        }

        // Цикл завершился, left > right. Это значит, что интервал поиска пуст.
        // Следовательно, target в массиве отсутствует.
        return -1;
    }
}

Ключевые детали реализации:
Переполнение безопасность: Формула left + (right - left) / 2 критична на массивах длиной более Integer.MAX_VALUE / 2. Хотя в Java массив не может иметь такой размер из-за ограничений JVM и индексов типа int, эта привычка переносится в языки с беззнаковыми индексами (C++, Rust) и показывает профессиональный уровень кодирования.
Инвариант цикла: Перед каждой итерацией выполняется условие — все элементы левее left гарантированно меньше target, все элементы правее right гарантированно больше target. Сохранение этого инварианта — залог корректности.
Точка выхода: Условие left <= right означает, что даже когда left == right, у нас остался один кандидат на проверку. Если его проверка не дает совпадения, на следующей итерации left станет больше right и цикл завершится.


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

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

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

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

Реализация и инварианты

public class InterpolationSearch {
    
    /**
     * Интерполяционный поиск для равномерно распределенных целочисленных данных.
     * ВНИМАНИЕ: требует, чтобы array[left] < array[right] и данные были равномерными!
     */
    public static int search(int[] array, int target) {
        if (array == null) throw new IllegalArgumentException("Array cannot be null");
        
        int left = 0;
        int right = array.length - 1;
        
        // Условие array[left] <= target <= array[right] критично для формулы
        while (left <= right && target >= array[left] && target <= array[right]) {
            // Если диапазон схлопнулся, переходим к линейному поиску
            if (array[left] == array[right]) {
                if (array[left] == target) return left;
                break; // Не найден
            }
            
            // Интерполяция позиции
            // Предотвращаем деление на ноль проверкой выше
            int mid = left + (target - array[left]) * (right - left) / (array[right] - array[left]);
            
            // Защита от выхода за границы (возможна при неравномерных данных)
            mid = Math.max(left, Math.min(mid, right));
            
            int midValue = array[mid];
            
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        
        // Пост-проверка границ
        if (left <= right && array[left] == target) return left;
        return -1;
    }
}

Критические условия применимости:
Равномерное распределение: Формула работает, если разность между соседними элементами примерно постоянна. Если данные сгущаются в некоторых зонах (например, 90% книг изданы в 2020-х, а остальные — растянуты на 50 лет), интерполяция будет постоянно ошибаться, откатываясь к бинарному поведению или хуже.
Отсутствие повторений на границах: Если array[left] == array[right], формула приводит к делению на ноль. В этом случае алгоритм должен деградировать к линейному поиску в этом поддиапазоне.
Целочисленное переполнение: Выражение (target - array[left]) * (right - left) может переполнить int при больших значениях. Для production-кода рекомендуется использовать long для промежуточных расчетов.


Анализ сложности и парадоксы

Средний случай: При равномерном распределении интерполяционный поиск достигает O(log log n). Это практически константа: для массива из 1 миллиарда элементов потребуется ~5 итераций. Это достигается за счет того, что каждый шаг не просто делит диапазон пополам, а приближается к цели экспоненциально быстро.

Худший случай: Если данные неравномерны (например, [1, 2, 3, 4, 5, 1000, 1001, 1002, 1003]), интерполяция может снова и снова попадать в «пустые» зоны, требуя O(n) сравнений. Это хуже бинарного поиска.

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


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

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

Практика

Сегодня мы применим знания о эффективном поиске на проекте «Библиотека».

Мы отсортируем список книг по названию, реализуем бинарный поиск для нахождения первой книги заданного автора (в отсортированном списке), и проведём сравнение времени выполнения линейного и бинарного поиска на коллекциях разных размеров. Это поможет наглядно увидеть преимущества логарифмического поиска O(log n) над линейным O(n), понять предпосылки (сортировка данных) и границы применимости (когда сортировка окупается).

Подготовка к уроку

Перед началом убедитесь, что проект готов, и вспомните ключевые концепции:
Бинарный поиск работает только на отсортированных данных, делит интервал пополам.
Линейный поиск — перебор O(n), всегда работает.
Сортировка O(n log n) — предпосылка для бинарного.

Откройте проект «Библиотека»: Убедитесь, что List<Book> books содержит достаточно книг (добавьте метод для генерации тестовых данных).
Импортируйте пакеты: java.util.Arrays (для бинарного поиска), java.util.Random (для генерации данных).
Генерация больших данных: Создайте метод generateBooks(int size) для создания списков размером 100, 10 000, 1 000 000 (используйте Random для title/author/year).


Отсортировать книги по названию

Обновите Book для Comparable (если не сделано): Реализуйте compareTo по title (this.title.compareTo(other.title)).
Создайте метод sortByTitle(): Используйте Collections.sort(books) — сортирует по Comparable (названию).
Вывод: После сортировки вызовите printAllBooks() для проверки.


Реализовать бинарный поиск для нахождения первой книги заданного автора

Отсортируйте по автору: Создайте Comparator<Book> byAuthor = Comparator.comparing(Book::getAuthor);, затем books.sort(byAuthor).

Реализуйте метод findFirstBookByAuthor(String author):
Используйте Arrays.binarySearch, но поскольку books — List, преобразуйте в массив или реализуйте вручную.

Вручную:

int low = 0, high = books.size() - 1; 

while (low <= high) {
        mid = (low + high) / 2; cmp = books.get(mid).getAuthor().compareTo(author);

        if (cmp < 0) low = mid + 1; 
        else if (cmp > 0) high = mid - 1;
        else { // Найден, найти первый: 
                  while (mid > 0 && books.get(mid-1).getAuthor().equals(author)) 
                  mid--; 
                  return books.get(mid); 
                } 
}

Если не найден — return null.

Проверка: После сортировки вызовите метод, выведите найденную книгу.


Сравнить время линейного и бинарного поиска на разных размерах

Реализуйте линейный поиск: Метод linearSearchByAuthor(String author) — for-each, если совпадение — return book.
Измерение времени: Используйте System.nanoTime() before/after.

Тест на размерах:
Для 100: generateBooks(100), sortByAuthor, time linear vs binary (поиск рандомного автора).
Для 10 000 и 1 000 000: Аналогично, усредните по 100 запускам.
Выводите: "Для n=[size]: Линейный: [time ns], Бинарный: [time ns]".

Анализ: Точка окупаемости сортировки + бинарный поиск vs множественный линейный поиск
Точка окупаемости — момент, когда стоимость сортировки + m бинарных поисков становится меньше m линейных поисков.

Расчёт:
Линейный: O(n) per search → m * n
Бинарный: O(n log n) sort + m * log n
Окупаемость: n log n + m log n < m n → m > (n log n) / (n - log n) ≈ log n (для больших n)
Пример: n = 1000, log n ≈ 10 — окупаемость после ~10 поисков.
n = 1 млн, log n ≈ 20 — после ~20 поисков.
Граница: Для малого m или n — линейный дешевле (нет сортировки).
В библиотеке: Если поиски редки — линейный; если часты — sort + binary.

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

Раздел 7. Алгоритмы

Глава 5: Рекурсия, деревья и введение в динамическое программирование

Принцип рекурсии и её опасности

Рекурсия — это методология решения задач, при которой функция вызывает сама себя для обработки подзадачи меньшего размера. В математике это называется рекуррентным соотношением, в программировании — рекурсивным вызовом. Главная идея состоит в том, чтобы свести решение сложной проблемы к решению аналогичной, но более простой проблемы, плюс некоторый шаг объединения результатов.

Представьте задачу вычисления суммы чисел от 1 до n. Итеративный подход использует цикл с аккумулятором. Рекурсивный подход говорит: сумма от 1 до n равна n плюс сумма от 1 до n-1. Это определение ссылается на само себя, но с меньшим аргументом. Такое самоподобие лежит в основе рекурсивного мышления.


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

Любая корректная рекурсивная функция строится на двух неразрывно связанных компонентах:
Базовый случай (base case) — это условие, при котором рекурсия останавливается и функция возвращает конкретное значение без дальнейших вызовов самой себя. Это точка выхода из бесконечного цикла вызовов. Без базового случая функция будет вызывать себя вечно, пока не исчерпает системные ресурсы. Для суммы чисел от 1 до n базовым случаем является ситуация, когда n равно 0 или 1 — сумма пустого множества или одного элемента тривиальна.
Рекурсивный шаг (recursive step) — это логика, связывающая результат текущего вызова с результатом вызова функции от модифицированных аргументов. Здесь кроется математическая индукция: мы предполагаем, что функция работает корректно для меньших входных данных (индукционная гипотеза), и доказываем, что тогда она работает для текущих данных.

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

Рассмотрим классический пример вычисления факториала. Математически n! определен как произведение всех натуральных чисел от 1 до n, с дополнительным условием 0! = 1.

public class RecursionFundamentals {

    /**
     * Вычисляет факториал числа n.
     * 
     * @param n неотрицательное целое число
     * @return n!
     * @throws IllegalArgumentException если n отрицательно
     */
    public static long factorial(int n) {
        // Базовый случай: факториал 0 или 1 равен 1
        // Это математическое определение, служащее якорем рекурсии
        if (n <= 1) {
            return 1;
        }
        
        // Защита от некорректного использования
        if (n < 0) {
            throw new IllegalArgumentException("Factorial undefined for negative numbers");
        }
        
        // Рекурсивный шаг: n! = n * (n-1)!
        // Здесь мы полагаемся на то, что factorial(n-1) вернет правильный результат
        // и умножаем его на n для получения текущего значения
        return n * factorial(n - 1);
    }
}

Инвариант рекурсии — условие, которое остается истинным на каждом уровне вызовов. Для факториала это утверждение, что при вызове factorial(k) мы находимся в процессе вычисления произведения чисел от k до n, где n — исходный аргумент верхнего уровня. Поддержание инварианта гарантирует корректность результата при возврате из глубины стека.


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