Какая сложность бинарного поиска

Бинарный поиск имеет временную сложность O(log n), где n — количество элементов в отсортированном массиве. Это связано с тем, что на каждом шаге алгоритм делит массив пополам, отбрасывая одну из частей.

Пространственная сложность:

• O(1) — если реализован итеративно (без рекурсии).
• O(log n) — если рекурсивно (из-за стека вызовов).

Пример итеративной реализации:

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