Preview

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
uploads/search1.png

  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?
uploads/bs9.jpg

  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 
IF the value is not found
OUTPUT "Value not found"

  Facebook Search

  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 6 is not found in the list

  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)?
uploads/insort.jpg

  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

  It doesn't output a message if an item is not found.

  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