Средняя производительность алгоритма бинарного поиска?

Question

http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance

BinarySearch(int A[], int value, int low, int high)
{
    int mid;
    if (high < low)
        return -1;
    mid = (low + high) / 2;
    if (A[mid] > value)
        return BinarySearch(A, value, low, mid-1);
    else if (A[mid] < value)
        return BinarySearch(A, value, mid+1, high);
    else
        return mid;
}

Если целое число, которое я пытаюсь найти, всегда находится в массиве, может ли кто-нибудь помочь мне написать программу, которая может вычислять среднюю производительность алгоритма двоичного поиска?

edit: я знаю, что могу сделать это, фактически запустив программу и посчитав количество вызовов, но здесь я пытаюсь сделать это без вызова функции.

edit2: KennyTM: Это сложность времени, я пытаюсь подсчитать среднее количество вызовов. Например, среднее число вызовов для поиска целого числа в A [2] будет равно 1,67 (5/3)

Answer 1

Вам не нужна «программа». Вы можете просто посчитать количество вызовов по методу BinarySearch.

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