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.
You might also like to view...
Where is the name of a file stored?
What will be an ideal response?
Shuffling a master item means that you are "unlocking" the item on the current page so that you can work with it.
Answer the following statement true (T) or false (F)
Which interface cannot be used for an external CD/DVD drive?
A) USB B) eSATA C) IEEE 1394 D) PATA
Which of the following scenarios will yield INACCURATE results long-term when using the PMT function.
a. When the interest rate changes monthly. b. Using an unequal number of months for the NPER. c. When the monthly payment is the same every month until the loan is repaid. d. When the interest rate is the same every month for the whole period.