Preview

04 - Binary Search #2 -additional questions

 1. Here's a step-by-step description of using binary search to play a guessing game. Can you suggest an appropriate line of pseudocode for Step 2. 
Let min = 0 and max = n-1.
_____________________________________________________________________________???
Compute guess as the average of max and min, rounded down (so that it is an integer).
If array[guess] equals target, then stop. You found it! Return guess.
If the guess was too low, that is, array[guess] < target, then set min = guess + 1.
Otherwise, the guess was too high. Set max = guess - 1.
Go back to step 2.

  If max > min, then stop: target is not present in the array. Return -1

  If max < min, then stop: target is not present in array. Return -1.

  If max > min, then stop: target is not present in the array. Return 1

  If max = min, then stop: target is present in array. Return 1

 2. Fill in the blanks for the below - how many, at most, would be required?
how_many_at_most_required.png

  6

  7

  16

  8

 3. What if 'n' isn't a power of 2? In that case, we can look at the ______________________

  closest lower power of 2. For an array whose length is 1000, the closest lower power of 2 is 512, which equals 2 to the power of 9.

  highest power of 2. For an array whose length is 1000, the highest power of 2 is 256

  problem in light of n-1 instead.

  problem using n x 2 instead. This will give us the closest lower power of 2 that can then be used.

 4. The 2014 "Catalogue of Life" contains about 1580000 names of species. If these names were sorted in an array, in the worst case, how long would it take to use binary search to find the name of a particular species in the array? 
Note: You may need a calculator for this one! Source: question taken from 'Khanacademy.org'

  At most, it would look at 79,000 names

  At most, it would look at 158000 names

  At most, it would look at 21 names

  At most, it would look at 6 names

 5. You have an array containing the prime numbers from 2 to 311 in sorted order: [2, 3, 5, 7, 11, 13, ..., 307, 311]. There are 64 items in the array. About how many items of the array would binary search have to examine before concluding that 52 is not in

  64

  5

  128

  7

 6. Binary search has a best case efficiency of O(1) and worst case (average case) efficiency of _______________

  O(nx2)

  O(n)

  O(log n)

  O(n-1)

 7. In general, if N is the size of the list to be searched and C is the number of comparisons to do so in the worst case, _________________

  C = log2N.

  C = logN

  C = 2N

  C = N

 8. Thus, the efficiency of binary search can be expressed as a _____________ function, in which the number of comparisons required to find a target increases _________ally with the size of the list.

  polynautical

  logarithmic

  exponential

  farcical

 9. The worst case number of comparisons is just 16 for a list with 100,000 items, versus 100,000 for linear search! Read the excerpt below and fill in the blanks 
Furthermore, if the list were doubled in size to 200,000, the maximum number of comparisons 
for binary search would only increase by 1 to 17, whereas for linear search it would ____
_________________________________________.

  double from 100,000 to 200,000

  stay the same at 100,000

  be halved from 100,000 to 50,000

  quadruple from 100,000 to 400,0000

 10. What is happening in the line: first = middle + 1; 
location = -1; 
first = 0; 
last = number of items in list minus 1;
 
while ((number of items left to search >= 1) and (target not found)) 
    middle = position of middle item, halfway between first and last 
    if (item at middle position is target) 
        target found 
    else 
        if (target < middle item) 
            search lower half of list next
            last = middle - 1; 
        else 
            #WHAT IS HAPPENING IN THE NEXT LINE?
            first = middle + 1; 
end while
 
if (target found) (i.e., middle item == target) 
    location = position of target in list (i.e., middle)
  
return location as the result

  It is aborting the operation as the item has not been found. 'first' variable is set to an unreachable value

  It is searching the lower half of the list again (recursive call)

  It is setting the 'first' variable to the the middle index number (which is always length of the list +1)

  It is searching the upper half of the list


Report an error