Searching Algorithms: Linear vs. Binary

Active learning works well for search algorithms because students grasp the speed difference only by physically counting steps and comparing results. When they see linear search struggle with large lists and binary search succeed, the contrast sticks better than abstract explanations ever could.

• Year 9
• Computing
• 4 activities
• 20 min–45 min

Learning Objectives

1. Compare the number of comparisons required by linear and binary search algorithms on a sorted list of 1000 items.
2. Predict scenarios where a linear search is more efficient than a binary search, justifying the choice.
3. Analyze the impact of a pre-sorted list on the performance and applicability of binary search.
4. Explain the time complexity difference between linear and binary search using Big O notation (O(n) vs. O(log n)).

Stations Rotation

⏱ 35 min·Small Groups

Card Sort Race: Linear vs Binary

Provide shuffled number cards (1-32) to groups. First, time linear searches for various targets. Sort the cards, then repeat with binary search, recording steps and times. Debrief on differences.

Prepare & details

Compare the efficiency of a linear search versus a binary search on a sorted list of 1000 items.

Facilitation Tip: During the Card Sort Race, circulate with a timer visible so students notice how quickly binary search narrows the field compared to linear search.

Setup: Tables/desks arranged in 4-6 distinct stations around room

Materials: Station instruction cards, Different materials per station, Rotation timer

• Remember
• Understand
• Apply
• Analyze
• Self-Management
• Relationship Skills

Stations Rotation

⏱ 45 min·Pairs

Coding Benchmark: Algorithm Duel

Pairs pseudocode both searches, then implement in Python. Test on lists from 10 to 1000 items, logging comparison counts. Graph results to visualize efficiency curves.

Prepare & details

Predict when a linear search might be more appropriate than a binary search.

Facilitation Tip: In the Coding Benchmark, ask students to print the midpoint value at each step to help them visualize binary search’s halving process.

Setup: Tables/desks arranged in 4-6 distinct stations around room

Materials: Station instruction cards, Different materials per station, Rotation timer

• Remember
• Understand
• Apply
• Analyze
• Self-Management
• Relationship Skills

Stations Rotation

⏱ 25 min·Small Groups

Scenario Debate: Pick the Search

Present real-world cases like finding a book in a library or contact in unsorted notes. Groups debate and justify linear or binary, then vote class-wide.

Prepare & details

Analyze how the requirement for a sorted list impacts the choice of search algorithm.

Facilitation Tip: In the Scenario Debate, require students to reference their step counts from earlier activities when justifying their choices.

Setup: Tables/desks arranged in 4-6 distinct stations around room

Materials: Station instruction cards, Different materials per station, Rotation timer

• Remember
• Understand
• Apply
• Analyze
• Self-Management
• Relationship Skills

Stations Rotation

⏱ 20 min·Individual

Prediction Sheets: Step Guesses

Individuals predict worst-case steps for linear and binary on lists of 16, 64, 512 items. Verify with teacher demo or apps, discuss surprises.

Prepare & details

Compare the efficiency of a linear search versus a binary search on a sorted list of 1000 items.

Facilitation Tip: Use Prediction Sheets to let students revise their initial guesses after seeing the data, reinforcing that predictions improve with evidence.

Setup: Tables/desks arranged in 4-6 distinct stations around room

Materials: Station instruction cards, Different materials per station, Rotation timer

• Remember
• Understand
• Apply
• Analyze
• Self-Management
• Relationship Skills

Teaching This Topic

Teach search algorithms by starting with physical demonstrations before coding. Have students sort cards and time their own searches to build intuition about efficiency. Avoid rushing to abstractions—let students experience the frustration of linear search on large lists firsthand. Research shows that kinesthetic activities like sorting cards or flipping coins to simulate halving create stronger mental models than slides alone.

What to Expect

Students will confidently explain when to use each algorithm, predict performance on different-sized lists, and justify their choices with clear reasoning. By the end, they should recognize that binary search saves time only when the list is sorted and only for larger datasets.

Watch Out for These Misconceptions

Common Misconception

During Card Sort Race, watch for students assuming binary search works on any list without sorting first. Correct this by giving them an unsorted deck and asking them to halve it—when they can’t, have them sort the deck first and try again to see the difference.

What to Teach Instead

During Coding Benchmark, watch for students assuming binary search is always faster. Correct this by timing both algorithms on small lists (e.g., 10 items) and asking students to explain why linear search might be adequate in those cases.

Common Misconception

During Scenario Debate, watch for students claiming binary search is always superior regardless of data size. Correct this by having them refer back to their Prediction Sheets and step counts for smaller lists.

What to Teach Instead

During Prediction Sheets, watch for students dismissing linear search for tiny datasets. Correct this by asking them to time both algorithms on 5-item lists and discuss practicality versus raw speed.

Common Misconception

During whole-class demos scaling from 100 to 10,000 items, watch for students thinking efficiency only matters for enormous datasets. Correct this by asking them to estimate how long linear search would take on their phone’s contact list versus binary search on a sorted version.

What to Teach Instead

During Scenario Debate, watch for students overlooking the prerequisite of a sorted list for binary search. Correct this by having them sort a small list mid-debate and rerun their chosen algorithm to see the impact.

Assessment Ideas

Quick Check

After Card Sort Race, give students a small unsorted list and a target. Ask them to count comparisons for linear search, sort the list, and count comparisons for binary search. Collect sheets to check accuracy of their counting and sorting steps.

Discussion Prompt

During Scenario Debate, listen for students to justify their choice of algorithm based on list size and sort status. Ask follow-up questions like, 'What if the list grows to 1 million items?' to probe their reasoning.

Exit Ticket

After Prediction Sheets, have students write one situation where linear search is better and one where binary search is superior, explaining their reasoning based on the step counts they recorded during the activities.

Extensions & Scaffolding

• Challenge students to modify their binary search code to count comparisons and graph the results for lists of 10, 100, 1000, and 10000 items.
• Scaffolding: Provide pre-sorted lists and labeled comparison counters for students who need help tracking steps.
• Deeper exploration: Ask students to research real-world examples where binary search is used (e.g., databases, autocomplete) and present findings to the class.

Key Vocabulary

Linear Search	An algorithm that checks each element in a list sequentially until the target value is found or the list ends.
Binary Search	An efficient algorithm that repeatedly divides the search interval in half, requiring the list to be sorted first.
Sorted List	A list where elements are arranged in a specific order, such as ascending or descending numerical or alphabetical order.
Time Complexity	A measure of how long an algorithm takes to run as the input size grows, often expressed using Big O notation.