Search Algorithms

An algorithm is...

• A set of steps to solve a problem
• When you sort data into the correct order
• When you search data for a specific value
• Any written code

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. 

As the data set grows in size, linear search becomes more efficient than binary search. 

• True
• False

What is the maximum number of comparisons a linear search algorithm could make while searching a 100 item list?

• 50
• 51
• 100
• 101

What is the average number of comparisons for a successful linear search on a list with 100 items?

• 50
• 101
• 100
• 50.5

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

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

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

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

• 1
• 2
• 3
• 4