# 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 the array. Return -1

If max < min, then stop: target is not present in 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? 8

6

16

7

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

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.

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

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 158000 names

At most, it would look at 79,000 names

At most, it would look at 6 names

At most, it would look at 21 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

128

64

7

5

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

O(n)

O(n-1)

O(log n)

O(nx2)

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

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 setting the 'first' variable to the the middle index number (which is always length of the list +1)

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

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

It is searching the upper half of the list