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

Бинарный поиск — принцип и реализация

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

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


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

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

Представьте отсортированный массив как монотонную функцию f(i) = array[i], где при увеличении индекса i значение не убывает. Это свойство монотонности гарантирует, что если array[mid] > target, то искомый элемент (если он вообще присутствует) не может находиться правее позиции mid. Аналогично для случая array[mid] < target. Это утверждение выполняется только в отсортированной последовательности.

Когда мы говорим о сортировке в контексте бинарного поиска, имеем в виду строгий порядок, поддерживаемый на всем диапазоне от array[0] до array[n-1]. Любое нарушение этого правила — и алгоритм начнет отбрасывать правильные ответы вместе с «плохими» половинами, возвращая ложные отрицательные результаты.


Ядро алгоритма: принцип деления пополам

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

Алгоритм состоит из циклически повторяющихся шагов:
Инициализация: Задаем два указателя — left, охватывающий начало рабочей области (обычно индекс 0), и right, обозначающий конец (последний допустимый индекс или размер массива в зависимости от вариации реализации).
Итерация: Пока область поиска не схлопнулась (left <= right или эквивалентное условие):
Вычисляем середину: mid = left + (right - left) / 2. Эта формула защищает от целочисленного переполнения, которое могло бы случиться при более прямолинейном (left + right) / 2 на очень больших массивах.

Сравниваем array[mid] с целевым значением target.
Если array[mid] == target — поиск успешен, возвращаем mid.
Если array[mid] < target — искомый элемент, если существует, находится строго правее. Сдвигаем left = mid + 1.
Иначе (array[mid] > target) — сдвигаем right = mid - 1.
Завершение: Если выход из цикла произошел без нахождения элемента, возвращаем индикатор отсутствия (обычно -1 или Optional.empty()).

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


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

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

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

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 #практика