# 05 - Searching Algorithms

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 / Binary

Binary / Linear

Linear / Insertion

Merge / Insertion

2. Mary wishes to use a binary search to search the following list of numbers for a specific number. Discuss This can't be done as a Binary search needs to be divided in half and this can't be.

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

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

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

3. The following shows a binary search for the number '9'. What is the next step in the algorithm? 9 will not be found as the Binary search stops at the mid point search

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

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

Bubble Search

Binary 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. linear sort

1. binary 2. linear

1. linear 2. binary

1. merge 3. sorted

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

The algorithm for both searches are equally complex

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

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

The algorithm is longer and more complex to write for a Linear 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 there is not an even number of items in the list

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

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`

Both Linear and Binary searches would be equally efficient

Linear Search would be more efficient on a short list

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, unsorted and static e.g. telephone number database, then a binary search is very fast compared to linear search.

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

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

This is true

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

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,7,15

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

2,3,9,12,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)```

All of the above are valid improvements

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

The code could be rewritten using only if statements

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 20 comparisons

None of the above

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

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 ?..

minimum times 'n' appears in the sequence

maximum times 'n' is repeated in the sequence

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

maximum number of times the while loop is executed