Computer Science
Grade 5
20 min
Searching for a Number: Linear Search vs. Guessing Game
Compare linear search (checking each number one by one) with a guessing game strategy for finding a specific number.
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define what an algorithm is in the context of searching.
Explain the step-by-step process of a Linear Search.
Explain the step-by-step process of a Binary Search (the 'Guessing Game').
Compare the number of steps (efficiency) between Linear Search and the Guessing Game on a sorted list.
Identify that the Guessing Game requires the list of numbers to be sorted first.
Trace the execution of both search algorithms on a small dataset.
Have you ever tried to find a specific word in a giant dictionary? 📖 How do you do it without reading every single word?
Today, we're going to learn about two different computer strategies, called algorithms, for finding a number in a list. We'll discover how one method is like looking one-by-one, and the o...
2
Key Concepts & Vocabulary
TermDefinitionExample
AlgorithmA list of step-by-step instructions that a computer follows to solve a problem or complete a task.A recipe for baking a cake is an algorithm. You follow the steps in order to get the final result.
Linear SearchAn algorithm that checks every single item in a list, one by one, from the beginning until it finds what it's looking for.To find the number 15 in the list [5, 20, 15, 10], you would check 5, then 20, and then find 15 on the third try.
Binary Search (The Guessing Game)A super-fast algorithm that finds an item in a SORTED list by repeatedly dividing the search area in half.To find a number between 1-100, you guess 50. If it's too high, you know the number is between 1-49 and you've eliminated half the options in one guess!
Sorted ListA li...
3
Core Syntax & Patterns
The Linear Search Rule: Check One by One
for each item in the list:
if item == target:
return 'Found it!'
Use a loop to go through each item starting from the very first one. In each step of the loop, use a conditional (an if-statement) to check if the current item is the one you're looking for.
The Guessing Game Rule: Split in Half
while the search area is not empty:
guess the middle item
if middle item is too high:
new search area = bottom half
else if middle item is too low:
new search area = top half
else:
return 'Found it!'
This only works on a sorted list! Instead of checking one by one, you always check the middle item of your current search area. Based on that guess, you can eliminate half of the remaining items.
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
The number of guesses needed for the Guessing Game (Binary Search) is related to the binary number system. Why is this?
A.Because computers can only count to 2.
B.Because each guess splits the problem into two choices (high/low), just like binary's two digits (0/1).
C.Because you can only search for the numbers 0 and 1.
D.Because the search only works on lists with two numbers.
Challenging
Imagine it takes a long time (10 minutes) to sort a list, but only a short time (1 second) to do a search. If you only need to find one number and will never use the list again, what should you do?
A.Sort the list, then use the Guessing Game.
B.Sort the list, then use Linear Search.
C.It doesn't matter which search you use.
D.Do not sort, just use Linear Search.
Challenging
A programmer makes a mistake in their Guessing Game code. Instead of guessing the middle element, their code always guesses the element at `low + 1`. How will this affect the search on a large, sorted list?
A.It will now work exactly like a Linear Search.
B.It will work, but it will be much slower than a correct Guessing Game.
C.It will be faster than a correct Guessing Game.
D.It will get stuck in an infinite loop.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free