1. Suppose the binary search is used to search for a number
$x$ in a sorted array of 80 numbers. Assuming that the array elements are
subscripted from 1 through 80, determine the exact number of comparisons
that the binary search algorithm will execute if $x$ occurs as the 17th
element in the array.
Here is the code with line numbers associated with statements (Stmt):
bool binary_search(A, lo, hi, x)|
1 if (lo > hi)
2 return false;
3 else
4 mid = (lo + hi) / 2;
5 if (A[mid] < x)
6 return binary_search(A, mid+1, hi, x);
7 else if (A[mid] > x)
8 return binary_search(A, lo, mid-1, x);
9 else
10 return true;
Initially I did an operation count as follows:
`
Stmt Stmt Stmt Stmt Stmt: Call
1 4 5 7 Count Params
(A,1,80,x)
1 False 2 mid=40 1 False 1 True 8:2 ret (A,1,39,x)
1 False 2 mid=20 1 False 1 True 8:2 ret (A,1,19,x)
1 False 2 mid=10 1 True 6:2 ret (A,11,19,x)
1 False 2 mid=15 1 True 6:2 ret (A,16,19,x)
1 False 2 mid=17 1 False 1 False 10:1 ret ret:TRUE
5 10 5 3 9 Total: 32
5 5 3 Comparisons: 13
However, the question asks for the comparison count. A strict construction of the requirement (Greg - how about that? I worked strict construction into the question. :-)) requires that only comparisons be counted. Statements 1, 5, and 7 are the only comparison statements. That is why the table looks that way. I plan to ask Dr. Asaithambi whether this is the correct interpretation. I suspect that it should be statements executed.