Computer Science · Grade 11

Active learning ideas

Linear Search and Binary Search

Active learning helps students grasp linear and binary search because abstract algorithm steps become concrete through code, movement, and timing. When students implement, simulate, and race algorithms, they directly experience why sorting matters and how efficiency changes with list size.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

• 20–45 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Collaborative Problem-Solving
• 30 min · Pairs

Coding Challenge: Implement Linear Search

Pairs write a linear search function in Python or JavaScript that returns the index of a target or -1 if not found. Test on lists of 10, 100, and 1000 elements, recording average search times. Discuss results and modify for worst-case scenarios.

Differentiate the conditions under which linear search is preferable to binary search.

Facilitation Tip

During the Linear Search Coding Challenge, have students print each comparison to the console so they see the sequential examination process.

What to look for

Present students with two scenarios: one describing a large, sorted list of customer IDs, and another describing a small, unsorted list of recently viewed items. Ask students to identify which search algorithm (linear or binary) would be more efficient for each scenario and briefly explain why.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 02

• Collaborative Problem-Solving
• 25 min · Small Groups

Physical Simulation: Binary Search Cards

Small groups sort a deck of 32 numbered cards face up. One student thinks of a number; others perform binary search by guessing the middle, narrowing halves each round. Time trials and record steps needed for different targets.

Analyze how data must be organized for binary search to be effective.

Facilitation Tip

For the Physical Simulation of Binary Search, use a deck of numbered cards and require students to verbally announce each step they take to the group.

What to look for

Facilitate a class discussion using the prompt: 'Imagine you are building a system to search through millions of song titles in a music library. What are the implications of sorting the data first for search efficiency, and how would that choice affect the algorithm you would use?'

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 03

• Collaborative Problem-Solving
• 45 min · Whole Class

Efficiency Race: Compare Algorithms

Whole class runs pre-written linear and binary search code on increasingly large sorted arrays. Students input datasets, log execution times in a shared spreadsheet, and plot graphs to visualize O(n) versus O(log n) growth.

Predict the performance of each search algorithm on a given dataset size.

Facilitation Tip

In the Efficiency Race, provide a mix of small, medium, and large arrays and ask groups to report both the actual runtimes and the number of comparisons made.

What to look for

On an index card, have students write down the primary condition required for binary search to function correctly. Then, ask them to describe one situation where linear search would be a practical choice despite its lower efficiency.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 04

• Collaborative Problem-Solving
• 20 min · Individual

Prediction Lab: Unsorted vs Sorted Data

Individuals predict search times for linear on unsorted data and binary on sorted data using given array sizes. Code to verify predictions, then adjust code to sort data and retest binary search.

Differentiate the conditions under which linear search is preferable to binary search.

Facilitation Tip

During the Prediction Lab, ask students to predict runtimes before testing so they confront their initial assumptions with real data.

What to look for

Present students with two scenarios: one describing a large, sorted list of customer IDs, and another describing a small, unsorted list of recently viewed items. Ask students to identify which search algorithm (linear or binary) would be more efficient for each scenario and briefly explain why.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

A few notes on teaching this unit

Teachers should emphasize that binary search is not just faster but fundamentally different in structure, using guided questions to contrast the two approaches. Avoid rushing to the final code; instead, model the first few steps of each algorithm on the board to build intuition. Research shows that kinesthetic activities like the card simulation improve retention of logarithmic behavior, so include at least one hands-on modeling task.

Successful learning looks like students confidently choosing the right search method for different data sets and explaining trade-offs in terms of time complexity. They should articulate why binary search requires sorted data and why linear search remains practical for small or unsorted collections.

---

Watch Out for These Misconceptions

• During the Physical Simulation: Binary Search Cards, watch for students assuming binary search works on unsorted data because the cards are visible at a glance.

  Have pairs scramble their cards and attempt binary search again, observing that the halving logic fails without sorted order. Ask each pair to explain why their search went wrong and how sorting fixes the process.

• During the Efficiency Race: Compare Algorithms, watch for students insisting linear search is always slower because binary search feels faster on large arrays.

  Provide small unsorted arrays in the race and ask students to time both algorithms, noting when linear search completes first. Discuss the cost of sorting as overhead that linear search avoids.

• During the Coding Challenge: Implement Linear Search, watch for students believing binary search halves the remaining elements by exactly half each time in all cases.

  After coding both, ask students to count the exact number of comparisons on a list of 15 elements for each algorithm and graph the results to see linear growth versus logarithmic steps.

---

Methods used in this brief

• Collaborative Problem-Solving