Searching and Sorting

Which type of lists or arrays are linear search algorithms typically used for?

• Unsorted

• Sorted

A binary search algorithm will ONLY work on a list which is in order.

• True

• False

Which one of the following is an advantage of a linear search?

• It takes a long time to find the item.
• It is a simple algorithm to write.
• It is more efficient than a binary search.
• It is a complex algorithm to write.

Using a binary search why will the number 9 never be found in the following list:

11, 8, 13, 9, 7, 3

• It does not work on numbers

• After checking if 9 is greater than 11 it will stop searching.

• The list is not in numerical order

• The first pass will take the first half because 13 is greater than 9, so the second half containing the 9 will be eliminated.

Which of the following descriptions best describes a linear search:

• Put the elements in order, check each item in turn
• Put the elements in order, compare with the middle value, split the list in order and repeat
• Elements do not need to be in order, check each item in turn.
• Elements do not need to be in order, compare to the middle value, split the list in order and repeat.

Which of the following best describes a binary search:

• Put the elements in order, check each item in turn.
• Put the elements in order, compare with the middle value, split the list in order and repeat
• Elements do not need to be in order, check each item in turn.
• Elements do not need to be in order, compare to the middle value, split the list in order and repeat.

A linear search is to be performed on the list:
12, 6, 8, 1, 3
How many searches would it take to find the number 1?

• 1
• 2
• 3
• 4

A binary search is to be performed on the list:
3, 5, 9, 10, 23
How many comparisons would it take to find the number 9?

• 0-1
• 2-3
• 4-5
• It can't be found

A bubble sort goes through two consecutive numbers at a time in a list and swaps them if not in order.

• True

• False

Which of the following describes a merge sort?

• Compares each pair and swaps

• List is split in two and merged together in order

• List is split into 2 and kept separate

• None of the above