Как достигается логарифмическая сложность операций

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

Примеры:

1. Бинарный поиск в отсортированном массиве:

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;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

2. Операции в сбалансированном бинарном дереве поиска (например, TreeMap, TreeSet) — вставка, удаление и поиск выполняются за O(log n), так как высота дерева логарифмически зависит от количества элементов.

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