← CS Unplugged

CS Unplugged activity

Trace a Search

About 20 minutesSoloPencil

Computers search through sorted lists all the time, like looking up a word in a dictionary. There are two common ways to do it. In this activity you will trace both by hand on the same list, and see which one wins.

How to trace it

  1. Look at the list of boxes below. It is sorted from smallest to largest.
  2. For Target 1, mark each box your linear search checks, left to right.
  3. Then mark each box your binary search checks. Start in the middle.
  4. Write how many checks each search took.
  5. For Targets 2 and 3, just write the counts. Don’t mark boxes again.

Finding the middle. Count how many boxes are left, then divide by two and round down. If 6 boxes are left, the middle is the 3rd one.

How it works: a worked example

This small list is not part of the exercise, just an example, with target 31. L1, L2, … marks a linear search, checking boxes left to right. B1, B2, … marks a binary search, starting in the middle:

1 5 L1
2 12 L2
3 19 L3B1
4 23 L4B2
5 31 L5B3

Linear took 5 checks. Binary took 3: it throws out half the boxes every time, since it knows the target must be bigger or smaller than the one it just checked.

Your turn

The list:

1 4
2 9
3 13
4 18
5 22
6 27
7 31
8 36
9 40
10 45
11 49
12 54
13 58
14 63
15 67

Target 1: 45.

Linear search: mark each box you check, in order.

1 4
2 9
3 13
4 18
5 22
6 27
7 31
8 36
9 40
10 45
11 49
12 54
13 58
14 63
15 67

Checks:

Binary search: start in the middle, then go left or right.

1 4
2 9
3 13
4 18
5 22
6 27
7 31
8 36
9 40
10 45
11 49
12 54
13 58
14 63
15 67

Checks:

Target 2: 67. Using the same list above, how many checks would each search take? Linear: Binary:

Target 3: 51. This number is not in the list. How many checks does each search take before it can be sure the number isn’t there? Linear: Binary:

Which was faster? Look at Target 1. Which search took fewer checks? Why do you think binary search can skip so many boxes?

Answer key

Target 1: 45. L marks a linear search check, B a binary search check, in order.

1 4 L1
2 9 L2
3 13 L3
4 18 L4
5 22 L5
6 27 L6
7 31 L7
8 36 L8B1
9 40 L9
10 45 L10B3
11 49
12 54 B2
13 58
14 63
15 67

Linear: 10 checks. Binary: 3 checks.

Target 2: 67. L marks a linear search check, B a binary search check, in order.

1 4 L1
2 9 L2
3 13 L3
4 18 L4
5 22 L5
6 27 L6
7 31 L7
8 36 L8B1
9 40 L9
10 45 L10
11 49 L11
12 54 L12B2
13 58 L13
14 63 L14B3
15 67 L15B4

Linear: 15 checks. Binary: 4 checks.

Target 3: 51 (not in the list). L marks a linear search check, B a binary search check, in order.

1 4 L1
2 9 L2
3 13 L3
4 18 L4
5 22 L5
6 27 L6
7 31 L7
8 36 L8B1
9 40 L9
10 45 L10B3
11 49 L11B4
12 54 L12B2
13 58 L13
14 63 L14
15 67 L15

Linear: 15 checks. Binary: 4 checks.

CC BY-NC-SA 4.0.