Объясните, что означает сложность алгоритма O(log n) и в каких случаях она применяется.

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

Такую сложность имеют алгоритмы, которые на каждом шаге уменьшают размер задачи примерно вдвое. Например:

• Бинарный поиск в отсортированном массиве — на каждом шаге отбрасывается половина элементов.
• Некоторые алгоритмы работы с деревьями (например, поиск в сбалансированном бинарном дереве).

Пример бинарного поиска на Java:

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; // не найдено
}

Здесь количество шагов поиска растёт примерно как log₂(n), где n — размер массива.