7.5 Search Algorithms

When can a Linear Search be performed?

• On letters

• On numbers

• Both

• None of these

In order to use a Binary Search, the data must be...

• int's or doubles

• either int's or Strings

• in order

• objects

True or False: Linear Search becomes more efficient as more values are added to a particular data set.

• True

• False

How does Linear Search work?

• Linear Search traverses an array, starting at the first element, until the desired value is found, or until the end of the array.

• Linear Search traverses an array from the last value to the first value until the desired value is found.

• Linear Search uses a while loop to traverse an array for the desired value, or until the end of the array.

• Linear Search searches for desired values by searching the next highest value in an array, and seeing if that is the desired value.

In a list with 100 items, how many comparisons are required by Sequential Search to determine that an item is not in the list?

• 50

• 100

• It may result in an infinite loop

• Not enough information to determine

How many iterations does Binary Search require to search a list with 32 items?

• 3

• 5

• 7

• It depends on whether the item is found or not.

Which of the following is the best description of the linear search algorithm?

• Put the elements in order, then go through them one by one until target is found or the end of the list is reached.
• Put the elements in order, compare with the middle value, if not the target: continue to the left or right of the middle and repeat. 
• Elements do not need to be in order. Go through them one by one until target is found or the end of the list is reached.
• Elements do not need to be in order, compare with the middle value, if not the target: continue to the left or right of the middle and repeat. 

Which of the following is the best description of the binary search algorithm?

• Put the elements in order, then go through them one by one until target is found or the end of the list is reached.
• Put the elements in order, compare with the middle value, if not the target: continue to the left or right of the middle and repeat. 
• Elements do not need to be in order. Go through them one by one until target is found or the end of the list is reached.
• Elements do not need to be in order, compare with the middle value, if not the target: continue to the left or right of the middle and repeat. 

What is the maximum number of comparisons required to find a value in a list of 20 items using a binary search?

• 20
• 5
• 6
• 21

How many comparisons would it take to find the value 7 in the following list using a linear search?
[1, 4, 7, 8, 5, 2, 9]

• 3
• 4
• 2
• Not possible, list is out of order