COMP1927 14s2

COMP1927 14s2 Final Exam

Computing 2

Question 4 (8 marks)

Consider the following recursive binary search function and a possible use-case for the function:

// return the index of element containing key in array a[]
// if key is not in the array, return -1
int bsearch(int key, int a[], int lo, int hi)
{
	ncalls++;
	if (lo > hi)
		return -1;
	else if (lo == hi) {
		if (key == a[lo])
			return lo;
		else
			return -1;
	}
	else {
		int mid = (lo+hi)/2;
		if (key < a[mid])
			return bsearch(key, a, lo, mid-1);
		else if (key > a[mid])
			return bsearch(key, a, mid+1, hi);
		else // (key == a[mid])
			return mid;
	}
}
...
int a[10] = {2,4,6,8,10,12,14,16,18,20};
int i, x, ncalls;
...
ncalls = 0;
i = bsearch(x, a, 0, 9);
printf("bsearch was called %d times\n",ncalls);

Based on the above answer the following questions:

1. What are the base cases for this recursion?

2. How many calls are made to the bsearch() function for each of the following values of x?

   1. x == 4
   2. x == 9
   3. x == 12

   (i.e. what is the value of ncalls after bsearch() returns its final result)

3. What are the smallest and largest number of calls to bsearch() needed to search in the above array (a[10])?

4. What are the smallest and largest number of calls to bsearch() needed to search in an array of size N?

Type the answer to this question into the file called q4.txt and submit it using the command:

$ submit q4

The above command will make a copy of q4.txt as your answer for this question.