Performance moyenne de l'algorithme de recherche binaire?

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

Si l'entier que je suis en train de trouver est toujours dans le tableau, quelqu'un peut-il me aider à écrire un programme qui permet de calculer le rendement moyen de l'algorithme de recherche binaire?

edit: Je sais que je peux le faire en exécutant le programme et en comptant le nombre d'appels, mais ce que j'essaie de faire ici, c'est de le faire sans appeler la fonction.

edit2: KennyTM: C'est une complexité temporelle, j'essaie de calculer le nombre moyen d'appels. Par exemple, le nombre moyen d'appels pour trouver un entier dans A [2], ce serait 1,67 (5/3)

Answer 1

Vous n'avez pas besoin d'un "programme". Vous pouvez simplement compter le nombre d'appels à la méthode BinarySearch.

Vous pouvez le faire facilement en passant un autre paramètre (par pointeur) ou en utilisant une variable globale. Dans ce cas - c'est un jouet - donc je vais probablement aller vite et sale avec le global.