Алгоритмнің 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 — размер массива.