In the binary search, if the array being searched has 32 elements in it, how many elements of the array must be examined to be certain that the array does not contain the key? What about 1024 elements? Note: the answer is the same regardless of whether the algorithm is recursive or iterative.

What will be an ideal response?

The binary search examines the midpoint of the array, then it examines the mid point
of half the array, then the midpoint of half that….until there is one element.
For 32 elements, it examines the midpoint. Then the midpoint of a 16 elements, then
the midpoint of 8, the midpoint of 4, the midpoint of 2 then the one element that is
left. That is 6 elements at most.
For 1024, this sequence is 1024, 512, 256, 128, 64, 32,16, 8, 4, 2, 1. At most 11
elements will be examined. Mathematically, this result is the floor of the base 2
logarithm of the number of elements. Note that this is an upperbound (a very good
one), but not always exact, since the size of the subarray is (n-1)/2 not n/2. The
difference is significant for smaller problems.