Searching: Linear Search vs. Binary Search

SubstitutePlans.com
Technology and Computer Science · Computer Science
SP-CS-013  ·  Free to print and use in your classroom  ·  substituteplans.com
Page 2
Searching: Linear Search vs. Binary Search
Technology and Computer Science · Computer Science · Grades 9-12 · 50 minutes
Time needed
50 minutes (one class period)
Prep
Copy the 2-page worksheet (one per student). Write the number-guessing example from
Before Class on the board.
Technology
None.
Student
independence
Medium. Students follow written rules, then compare answers with a partner.
Copies to make
One 2-page worksheet per student
Materials
Pencils, Worksheet, Whiteboard or chalkboard
Goal for today: Students will carry out linear and binary search on a sorted list, count the checks each method needs,
and explain why binary search needs the list to be sorted.
Before the bell
☐ Copy the worksheet, one per student (2 pages).
☐ On the board write: “I am thinking of a number from 1 to 100.” Be ready to play one quick round of
higher/lower guessing if students need the idea.
☐ Keep the answer key on your desk. You do not need to solve the problems yourself.
☐ Make sure students know they will not need computers or calculators.
Say this to start
Good morning! Searching is something computers do millions of times a second: finding a name, a song, a word. Today
you will try two ways to search a list and count how many steps each takes. One method is slow but simple. The other
is clever and much faster, but only works if the list is in order. Follow the rules on your worksheet exactly and keep
count of every number you look at.


SubstitutePlans.com
Technology and Computer Science · Computer Science
SP-CS-013  ·  Free to print and use in your classroom  ·  substituteplans.com
Page 3
Run of show
Minutes
What you do
What students do
0–5
Take attendance. Hand out the worksheet and ask
students to read the rules box.
Read the rules for linear search and binary
search.
5–13
Play one round of the guessing game: pick a secret number
from 1 to 100 on paper (do not say it). Have the class
guess by always choosing the middle of what is left, and
say only “higher” or “lower.” Point out that each guess
throws away half of the possibilities.
Take turns guessing and notice how fast
the range shrinks.
13–25
Tell students to complete questions 1–6 about the sorted
list. Walk the room and check that they are counting every
item they look at.
Count the checks for each method.
25–33
Tell students to fill in the binary search table for the
number 71 (Part B) and answer question 7.
Follow the rules step by step and fill in the
table.
33–44
Tell students to finish the rest of the worksheet (questions
8–14). Partners may compare the Biggest list table.
Complete the doubling table and the
remaining questions.
44–48
Read answers to questions 1–7 and the tables aloud from
the key. Students check their work.
Mark and correct answers.
48–50
Collect all worksheets.
Hand in the worksheet.
If things go wrong
• If students are unsure how to find the middle, tell them: add low and high, divide by 2, and drop any decimal.
For low 0 and high 14, the middle index is 7.
• If students get different counts, have them list every number they looked at, in order. The count is the length
of that list.
• If a student says linear search is better for finding 3, they are right. That is the key idea: linear can win when
the target is at the very front.
• If the guessing game gets silly, move straight to the worksheet and use the table as the model.
Early finishers
• Design a sorted list of 7 numbers and a target that binary search finds on the very first check. Write them
down.
• Explain in two sentences why a million-item list needs only 20 checks with binary search.
• Write a sorted list of 7 words (alphabetical order) and describe how binary search would find the fifth word.
Support and challenge
• Support: Let students do questions 1–4 and 7–9, and use their finger to mark which part of the list is still “in
play” during binary search.
• Challenge: Ask students to extend the Biggest list table and work out how many checks binary search needs
for 1,000,000 items (20).


SubstitutePlans.com
Technology and Computer Science · Computer Science
SP-CS-013  ·  Free to print and use in your classroom  ·  substituteplans.com
Page 4
Notes for the teacher (you fill this in)
Jot a few lines before you leave. A full Daily Sub Report is in the free Sub Survival Kit at SubstitutePlans.com.
How far the class got / what to pick up next:
Students who were especially helpful:
Anything the teacher should know: