Linear and binary search

Overview

How linear and binary searches work, why a binary search needs sorted data, the midpoint calculation, worked searches through short lists, and the strengths of each.

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 how a linear search works.

   Model answer

   A linear search checks each item in a list in turn, starting with the first. The search stops when the target is found or every item has been checked.

2. 2

   What must be true of the data before a binary search can be used?

   Model answer

   The data must already be sorted into order. A linear search has no such requirement and works on unsorted data.

3. 3

   Describe how a binary search works.

   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.

4. 4

   How is the middle position calculated in a binary search?

   Model answer

   The middle position is (low + high) DIV 2. The values low and high are the first and last positions still being searched. DIV discards any remainder, so the midpoint rounds down.

5. 5

   In a binary search, what happens to low and high when the target is greater than the middle item?

   Model answer

   The value of low is set to mid + 1, and high stays the same. The middle item and everything below it are discarded.

6. 6

   A linear search looks for 15 in [8, 3, 15, 6, 11]. Which items are checked?

   Model answer

   The search checks 8, then 3, then 15. The target is found at index 2 after three comparisons.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.