1. Consider the following C/C++ function.

int search( int x, int list[], int left, int right )

{

int result;

int mid = (left + right) / 2;

if (x == list[mid])

result = mid;

else if (x < list[mid] && left < mid)

result = search( x, list, left, mid-1 );

else if (x > list[mid] && mid < right)

result = search( x, list, mid+1, right );

else

result = -1;

return result;

}

a) Give the big-O classification of the function: ____O(log₂n)___________

b) Using the function, complete the following chart to show the number of steps required to find each of the values. Note that a step is defined to be one computation of variable mid.

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
value	100	110	120	130	140	150	160	170	180	190	200	210	220	230	240
steps

c) Based on the completed chart, give each of the following in terms of number of steps when the search key is found.

Best case: _____1_______

Worst case: _____4_______

Average case: ____________

d) How many steps are required when the search key is not found in the list? ____4________