Question

Оценить сложность блока кода:
int recFunc(int i, int j, int needsToFind)
{
int mid;
mid = (i + j) / 2;
if(a[mid] == needsToFind) return mid;
else
{
if(a[mid] > needsToFind) return recFunc(i, mid, needsToFind);
else return recFunc(mid, j, needsToFind);
}
}

Примечания:
Код вызывается с такими параметрами recFunc(1, N, k), где N - это размер массива, а k - искомый элемент.
Массив a - глобальный, отсортированный по неубыванию

Answer 1

Данный код - это рекурсивный бинарный поиск

Так как мы при повторном вызове функции взаимодействуем лишь с половиной массива, то можем смело сказать что сложность алгоритма - log(N)

Ответ: O(log(N))

Если не правильно, то извините