Searching Algorithms: Linear and Binary Search

Active learning helps students grasp how linear and binary search behave in real code rather than memorizing definitions. By coding, racing, and debating, they experience the trade-offs between simplicity and speed firsthand, building lasting intuition for when each algorithm fits.

• Year 11
• Computing
• 4 activities
• 20 min–35 min

Learning Objectives

1. Compare the time complexity of linear search and binary search algorithms using Big O notation.
2. Analyze the performance of linear and binary search on datasets of varying sizes and states (sorted vs. unsorted).
3. Justify the selection of an appropriate search algorithm (linear or binary) based on data characteristics and problem constraints.
4. Implement both linear and binary search algorithms in a chosen programming language or pseudocode.
5. Evaluate the trade-offs between algorithm simplicity and efficiency for searching tasks.

Stations Rotation

⏱ 25 min·Pairs

Pair Programming: Linear Search Code-Off

Pairs write a linear search function in Python and test it on unsorted lists of 10, 100, and 1,000 items. They time runs using time module and graph results. Discuss findings: why does time grow linearly?

Prepare & details

Compare the efficiency of linear search versus binary search for sorted data.

Facilitation Tip: During the Pair Programming Linear Search Code-Off, circulate and ask each pair to verbalize the loop condition and comparison before running the code to reinforce trace skills.

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

⏱ 35 min·Small Groups

Small Groups: Binary Search Race

Groups implement binary search on sorted arrays, compare runtimes against linear search on the same data. Use stopwatches for manual simulations first, then code. Predict and verify halvings per step on a projector.

Prepare & details

Predict the performance of a linear search on a very large, unsorted dataset.

Facilitation Tip: In the Binary Search Race, provide identical datasets to each small group so results are comparable, and insist on a written record of each mid-point calculation.

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·Whole Class

Whole Class: Efficiency Debate

Project real-world scenarios like phone contacts or library catalogs. Class votes on best algorithm, justifies with prior timings. Teacher tallies and reveals optimal choices based on sorted/unsorted status.

Prepare & details

Justify when a linear search might be preferred over a binary search.

Facilitation Tip: For the Efficiency Debate, assign roles (linear advocate, binary advocate, data analyst) so every student has a stake in the reasoning, not just the confident speakers.

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

⏱ 30 min·Individual

Individual: Prediction Challenge

Students predict search times for datasets before coding tests. Run linear and binary on their machines, log discrepancies in a table. Share surprises in plenary.

Prepare & details

Compare the efficiency of linear search versus binary search for sorted data.

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 binary search by starting with a physical number line and a volunteer ‘searcher’ to model halving steps, then move to pseudocode before coding. Avoid rushing to the logarithm formula; instead, have students count steps on small lists until the pattern emerges. Research shows that concrete-to-abstract sequencing prevents the ‘magic trick’ feeling many students report with binary search.

What to Expect

Students will confidently implement both algorithms, justify their choices based on dataset size and order, and articulate the difference between O(n) and O(log n) complexity. They will use timing data and step counts to explain rather than guess which algorithm suits which problem.

Watch Out for These Misconceptions

Common Misconception

During the Binary Search Race, watch for students who run the algorithm on unsorted lists without sorting first, producing incorrect results.

What to Teach Instead

Pause the race and ask each group to verify their list is sorted by checking adjacent pairs before re-running; this reinforces that binary search relies on sorted data.

Common Misconception

During the Pair Programming Linear Search Code-Off, watch for students who assume linear search is always slower than binary search even on tiny unsorted lists.

What to Teach Instead

Have each pair time their linear search on a list of 5 items versus their binary search attempt on the same unsorted list to see binary fail and linear succeed, then discuss preprocessing trade-offs.

Common Misconception

During the Efficiency Debate, watch for students who describe binary search as checking every other item like a skip-list.

What to Teach Instead

Use the number line visualization from the binary search demo to show how each step eliminates half the remaining items, not just one, and ask students to redraw their steps to match.

Assessment Ideas

Quick Check

After the Pair Programming Linear Search Code-Off, present students with a small unsorted list and target. Ask them to trace linear search steps on paper, count comparisons, and explain why binary search cannot be used without sorting.

Discussion Prompt

During the Efficiency Debate, pose the scenario of a 10,000-item sorted website list and ask students to defend their algorithm choice using timing data from their races, then consider the impact of an unsorted list.

Exit Ticket

After the Binary Search Race, ask students to write one advantage of linear search and one advantage of binary search, then predict which would be faster for a phone book versus a scrambled paragraph and justify their choices.

Extensions & Scaffolding

• Challenge early finishers to implement a hybrid search that uses binary search on the sorted portion of a partially sorted list and linear search for the rest.
• Scaffolding: Provide partially completed trace tables for binary search with missing mid-point calculations so students focus on reasoning rather than generating code.
• Deeper exploration: Ask students to research interpolation search and present a short comparison to binary search, including when each shines.

Key Vocabulary

Linear Search	A sequential search algorithm that checks each element of a list or array until a match is found or the whole list has been searched.
Binary Search	An efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
Time Complexity	A measure of how long an algorithm takes to run as a function of the size of the input, often expressed using Big O notation.
Big O Notation	A mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, commonly used to classify algorithms by their running time or space requirements.
Sorted Data	Data that has been arranged in a specific order, such as ascending or descending, which is a prerequisite for algorithms like binary search.