Hello,
I have a program which searches for (using binary search) specific word in ordered list and counts number of comparisons it makes until it finds the target!
My problem is: how can I count average of number of comparisons?
Here is how searching function works:
int binary_search(char *array[], int end, char *target, int *location, int *compare_count){
int first;
int middle;
int last;
first = 0;
last = end;
*compare_count = 0;
while(first <= last){
middle = (first + last)/2;
if(strcmp(array[middle], target) < 0){
first = middle + 1;;
}
else if(strcmp(array[middle], target) > 0){
last = middle - 1;
}
else
break;
(*compare_count)++;
}
*location = middle;
if(first == last) first--;
return(strcmp(target, array[middle]) == 0);
}