Linear search and binary search

Overview

How linear and binary searches work, why a binary search needs a sorted list, choosing the middle item, traced searches through short lists, worst cases, and when each search 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 a list in turn, starting with the first. The search stops when the item is found or when the list runs out.

2. 2

   Does a linear search need the list to be sorted?

   Model answer

   A linear search works on a sorted or an unsorted list. The search simply compares every item with the target until it finds a match.

3. 3

   A linear search looks for 9 in the list [4, 7, 9, 2]. Which items are compared?

   Model answer

   The search compares 4, then 7, then 9. The item is found on the third comparison, so 2 is never checked.

4. 4

   A linear search looks for 6 in the list [4, 7, 9, 2]. How many comparisons are made?

   Model answer

   The search makes four comparisons, one with every item. The value 6 is not in the list, so the search reports that it was not found.

5. 5

   What is the worst case for a linear search?

   Model answer

   The worst case is when the target is the last item or is not in the list. Every item must then be compared.

6. 6

   How does a binary search work?

   Model answer

   A binary search compares the target with the middle item of a sorted list. The half that cannot contain the target is discarded. The search repeats on the remaining half until the item is found or none are left.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.