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