Можешь назвать алгоритмы, основанные на методе бинарного поиска, и объяснить их особенности?

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

• Классический бинарный поиск — ищет элемент в отсортированном массиве за O(log n). Работает только на отсортированных данных.

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

• Поиск в бесконечном или неизвестного размера массиве — сначала расширяем границы поиска экспоненциально, затем применяем бинарный поиск.

• Поиск корня уравнения (метод половинного деления) — применяется для поиска корня функции на отрезке, где функция меняет знак.

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

Пример бинарного поиска в Java для поиска элемента в отсортированном массиве:

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // элемент не найден
}