Preview

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

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

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

  Linear Search

  Bubble Search

  Binary Search

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

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

  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

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

  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