Linear search

Overview

Recall questions on the linear search algorithm, tracing successful and unsuccessful searches, best, average and worst-case and space complexity, unsorted data and linked lists, when linear search is the right choice, and checking for the end.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe the linear search algorithm.

   Model answer

   Start at the first item of the list and compare it with the target value. If it matches, report the position and stop. If not, move to the next item and repeat. If the end of the list is reached without a match, report that the item is not present.

2. 2

   Trace a linear search for 7 in the list 4, 9, 2, 7, 5 and count the comparisons.

   Model answer

   Compare 4 with 7: no match. Compare 9: no. Compare 2: no. Compare 7: match, so the search reports position four and stops without looking at 5. Four comparisons were needed.

3. 3

   Trace a linear search for 6 in the list 4, 9, 2, 7, 5.

   Model answer

   Every item is compared in turn: 4, 9, 2, 7 and 5, none of which matches. The end of the list is reached, so the search reports that 6 is not present. Five comparisons were needed, which is the maximum for a list of five items.

4. 4

   State the best, average and worst-case complexity of a linear search.

   Model answer

   Best case O(1), when the target is the very first item. Worst case O(n), when the target is the last item or is not present at all, since every item must be checked. Average case O(n), because on a successful search of randomly placed data about half the list is examined, and half of n still grows in proportion to n.

5. 5

   What is the space complexity of a linear search?

   Model answer

   O(1). It needs only a counter for the current position and a copy of the target value, no matter how large the list is, and it does not modify or duplicate the data.

6. 6

   Does a linear search require the list to be in any particular order?

   Model answer

   No. It makes no assumption about order and simply examines every item until it finds the target or runs out. This is its main advantage over binary search, which cannot be used at all unless the data is sorted.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.