Бинарлы іздеу әдісіне негізделген алгоритмдерді атаңыз және олардың ерекшеліктерін түсіндіріңіз.

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

• Классический бинарный поиск — ищет элемент в отсортированном массиве за 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; // элемент не найден
}