Average performance of binary search algorithm?
- by Passionate Learner
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;
}
If the integer I'm trying to find is always in the array, can anyone help me write a program that can calculate the average performance of binary search algorithm? I know I can do this by actually running the program and counting the number of calls, but what I'm trying to do here is to do it without calling the function. I'm not asking for a time complexity, I'm trying to calculate the average number of calls. For example, the average number of calls to find a integer in A[2], it would be 1.67 (5/3).
