Searching and sorting algorithms

Overview

Linear and binary searches traced through short lists, worst-case compares, and bubble and merge sorts worked step by step, with when each is the better choice.

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

   How does a linear search work?

   Model answer

   A linear search checks each item in turn, starting from the first. The search stops when the target is found or the end of the list is reached.

2. 2

   How does a binary search work?

   Model answer

   A binary search compares the target with the middle item of a sorted list. Half of the remaining list is discarded after each compare, until the target is found or nothing remains.

3. 3

   What condition must a list meet before a binary search can be used?

   Model answer

   The list must already be sorted into order. A binary search on an unsorted list can miss an item that is present.

4. 4

   A linear search looks for 9 in the list 4, 7, 1, 9, 3. State how many compares it makes.

   Model answer

   The search makes 4 compares. The values 4, 7 and 1 are checked before 9 is found.

5. 5

   A binary search looks for 23 in the sorted list 3, 8, 12, 15, 23, 31, 40, choosing the middle item each time. Which items are compared?

   Model answer

   The search compares 15, then 31, then 23. The target is found on the third compare.

6. 6

   A binary search looks for 30 in the sorted list 4, 9, 16, 25, 36, 49, 64. Which items are compared before the search reports that 30 is absent?

   Model answer

   The search compares 25, then 49, then 36. The remaining sub-list is then empty, so the search reports that 30 is not in the list.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.