import java.util.*;

public class Task230126 {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("apple", "banana", "grape", "orange");
        int index1 = Collections.binarySearch(list, "grape");
        int index2 = Collections.binarySearch(list, "kiwi");
        System.out.println("Grape: " + index1);
        System.out.println("Kiwi: " + index2);
    }
}

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

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
    }
}

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;
    }
}

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;
}

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

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;
    }
}

public class Task260126 {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 1000};
        int index = interpolationSearch260126(arr, 2);
        System.out.println(index);
    }

    static int interpolationSearch260126(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low <= high && target >= arr[low] && target <= arr[high]) {
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
            
            if (arr[pos] == target) return pos;
            if (arr[pos] < target) low = pos + 1;
            else high = pos - 1;
        }
        return -1;
    }
}

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); 
                } 
}