Searching algorithms

Overview

Recall questions on linear and binary search, their time complexities, the number of comparisons each makes, and tracing a search that succeeds and one that fails.

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 in the list. Compare it with the value being searched for. If they match, the search succeeds and the position is returned. If not, move to the next item and repeat. If the end of the list is reached without a match, the value is not present and the search fails.

2. 2

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

   Model answer

   Compare 4 with 9 — no match. Compare 7 with 9 — no match. Compare 2 with 9 — no match. Compare 9 with 9 — match found at position 4 (index 3). The search took four comparisons.

3. 3

   What is the time complexity of linear search, and what does it mean?

   Model answer

   O(n). In the worst case, when the item is the last in the list or is not present at all, every one of the n items must be examined, so the time taken grows in direct proportion to the number of items. Doubling the length of the list doubles the expected time.

4. 4

   How many comparisons does a linear search make in the best, average and worst cases?

   Model answer

   Best case: 1 comparison, when the item is the first in the list. Worst case: n comparisons, when it is the last item or is absent. Average case for a successful search: about n/2 comparisons. The best case is O(1), since a single comparison does not grow with n at all. The average and worst cases are both O(n), because constant factors are ignored in complexity, which is why linear search is quoted as O(n).

5. 5

   When would you choose a linear search?

   Model answer

   When the data is unsorted, because linear search is the only one of these algorithms that does not require sorted data. Also when the list is short, where the simplicity of the algorithm outweighs any speed advantage of binary search, and when the data is held in a structure such as a linked list that cannot be accessed directly by index.

6. 6

   Describe the binary search algorithm.

   Model answer

   The list must already be sorted. Examine the middle item of the list. If it is the value being searched for, the search succeeds. If the value is smaller than the middle item, discard the middle item and everything after it and repeat on the lower half; if it is larger, discard the middle item and everything before it and repeat on the upper half. Continue until the value is found or the section left to search is empty, in which case the value is not present.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.