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

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; 
} 

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

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

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

Answer 1

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

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