# 05 - Searching Algorithms #2

1. 1. _____________ search: Each item in the list is checked in order. 2. __________ search: An ordered list is divided in 2 with each comparison.

Linear / Insertion

Binary / Linear

Linear / Binary

Merge / Insertion

2. Mary wishes to use a binary search to search the following list of numbers for a specific number. Discuss

This can be done although a Linear search would be much faster.

This can't be done as a Binary search needs to be divided in half and this can't be.

This can be done and a Binary search is the most efficient option

This cannot be done as a Binary search only works on a sorted list

3. The following shows a binary search for the number '9'. What is the next step in the algorithm?

16 > 9 so make a new list with the numbers: 2,6,9,12

9 will not be found as the Binary search stops at the mid point search

16 > 5 so make a new list with the numbers: 1,2,3,4

16 < 6 so make a new list with the numbers: 1,2,3,4

4. The following pseudo-code describes what type of search?
```Check the first value
IF it is the value you are looking for
STOP
ELSE move to and check the next value
REPEAT UNTIL you have checked all the elements and not found the value
```

Linear Search

Binary Search

Bubble Search

5. The length of the search is very important for obvious reasons. In a __________ search the worst case scenario is you have to check half the values and in a __________ search the worst case scenario is you have to check all the values.

1. linear 2. binary

1. binary 2. linear

1. linear. 2. linear sort

1. merge 3. sorted

6. Compare the algorithms for a Linear and Binary Search. Which of the following statements is true?

The algorithm is so easy for a linear search that it doesn't need to be written

The algorithm for both searches are equally complex

The algorithm is longer and more complex to write for a Linear Search

The algorithm is longer and more complex to write for a Binary Search

7. Can you explain why the following algorithm, when run, produces the output: "FALSE"?

because a binary search cannot be performed on this list

because this is a linear search and the mid point cannot be found

because there is not an even number of items in the list

8. Given the following list, you are searching for the name 'Adam'. Would it be easiest/best/most efficient to use a Linear or Binary Search?
`Adam,Eve,Seth`

Linear Search would be more efficient on a short list

Both Linear and Binary searches would be equally efficient

Binary Search is always more efficient, especially on a very short list

Neither search would be adequate as the list only has 3 elements

9. You are given a random list of student scores. It is best to use a Binary Search in this case.

False

True

10. If the list is large and static e.g. telephone number database, then a binary search is very fast compared to linear search.

This is false because you can't do a binary search on a list with telephone numbers

This is false because a binary search is always slower than a linear search

This is false because a binary search is only done on very small lists

This is true

11. The following shows an insertion sort and the stages involved. What is the output in the next stage? (what sequence of numbers)?

2,3,9,12,15

2,3,9,12,15,2,7,15

3,9,12,15,2,7,15

3,12,9,15,2,7,15

12. Below is the algorithm for a linear search. What is missing? (or what could be added to further improve the algorithm?)
```PROCEDURE sort(list,INPUT)
size = len(list)
For i from 0 to size-1 DO
If list[i] = INPUT
OUTPUT Found item

list = Jim, Fred, Sue, Sheila
INPUT Enter item to search for
sort(list,INPUT)```

There is no list to search from which will cause the program to crash

The code could be rewritten using only if statements

All of the above are valid improvements

13. A user has a database of 100,000 people and needs to search through to find one person. In a linear search the ?.

worst case scenario would be 100,000 comparisons / all values checked.

worst case scenario would be 20 comparisons

None of the above

worst case scenario would be 100,000 / n which is 10.

14. This technique iterates over the sequence, one item at a time, until the specific item is found or all items have been examined

Bubble Search

Iteration Search

Linear Search

Binary search

15. To evaluate the efficiency of the the binary search algorithm, assume the sorted sequence contains n items. We need to determine the ?..

maximum number of times the while loop is executed

minimum + maximum times that the loop is repeated which gives us the efficiency factor

maximum times 'n' is repeated in the sequence

minimum times 'n' appears in the sequence