Computer Science · Grade 10 · Algorithms and Logical Decomposition · Term 1

Searching Algorithms (Linear & Binary)

Compare and contrast linear and binary search algorithms, understanding their efficiency and use cases.

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

About This Topic

Searching algorithms teach students to locate data efficiently in lists, a key skill in programming. Linear search checks each element from start to end until the target appears or the list finishes. It suits unsorted data or small lists but slows with size. Binary search works on sorted lists by comparing the target to the middle element, then searching half the list, repeating until found. This halves the space each step, ideal for large datasets.

In Ontario's Grade 10 Computer Science curriculum, students compare step counts for both on sample lists, analyze efficiency based on list size and order, and decide use cases. This builds logical decomposition and introduces time complexity ideas without formal Big O notation yet.

Active learning turns comparisons into experiences students own. When they code both algorithms, time runs on growing lists, or simulate with physical cards, performance gaps become visible. Groups debating results refine choices, while debugging code fosters persistence and precision.

Key Questions

1. Compare the efficiency of linear search versus binary search.
2. Analyze when to apply each searching algorithm based on data characteristics.
3. Construct a simple searching algorithm to find an element in a list.

Learning Objectives

• Compare the number of comparisons required by linear search and binary search for a given dataset size.
• Analyze the efficiency of linear search and binary search based on whether the input list is sorted.
• Construct a Python function to implement a linear search algorithm.
• Design a scenario where binary search is a more appropriate choice than linear search.
• Evaluate the trade-offs between implementation simplicity and performance for searching algorithms.

Before You Start

Introduction to Lists and Data Structures

Why: Students need a foundational understanding of how to store and access elements within a list before they can search through it.

Basic Programming Constructs (Loops and Conditionals)

Why: Implementing search algorithms requires the use of loops to iterate through elements and conditional statements (if/else) to check for matches.

Key Vocabulary

Linear Search	A sequential search algorithm that checks each element in a list one by one until the target value is found or the list ends. It works on both sorted and unsorted lists.
Binary Search	An efficient search algorithm that repeatedly divides the search interval in half. It requires the input list to be sorted.
Sorted List	A list where elements are arranged in a specific order, such as ascending or descending. This order is crucial for binary search to function correctly.
Comparison	A single operation where the search algorithm checks if the current element matches the target value or if the target is greater or less than the current element.

Watch Out for These Misconceptions

Common Misconception

Binary search works on any list, sorted or not.

What to Teach Instead

Binary search fails on unsorted lists because mid-point comparisons lead to wrong halves. Small group card activities show failed searches on shuffled decks, prompting sorts first. Peer explanations during rotations correct this hands-on.

Common Misconception

Linear search is always slower, even for small lists.

What to Teach Instead

Overhead of binary setup makes it comparable or slower for tiny lists. Pairs timing code on 5-10 item lists reveal this, shifting focus to scale. Discussions refine when simplicity trumps speed.

Common Misconception

Computers are so fast efficiency does not matter.

What to Teach Instead

Scale matters in big data; linear on millions crashes time limits. Whole class visualizations of exploding steps build real-world awareness. Students connect to apps they use daily.

Active Learning Ideas

Pairs Coding: Build and Test Searches

Pairs write linear and binary search functions in Python or pseudocode. Test on unsorted and sorted lists of 20, 200, and 2000 elements, counting steps or using time functions. Pairs graph results and present one insight to class.

35 min·Pairs

Small Groups: Card Deck Simulations

Provide decks of numbered cards, some sorted, some shuffled. Groups perform linear searches on shuffled decks and binary on sorted ones, recording steps per search. Switch decks and compare averages as group sizes grow.

30 min·Small Groups

Whole Class: Live Visualization Race

Display a large sorted list on screen. Class votes predictions on steps for linear versus binary to find a target. Run step-by-step animations for both, tally class predictions versus actuals, discuss surprises.

20 min·Whole Class

Individual: Use Case Analysis

Students get scenarios like phonebooks or playlists. Decide and sketch linear or binary search, justify with efficiency reasons. Share one via exit ticket for class review next lesson.

15 min·Individual

Real-World Connections

• Librarians use search algorithms to quickly locate specific books within a library catalog, whether the catalog is sorted by title, author, or Dewey Decimal System number.
• Online retailers like Amazon employ search algorithms to find products from millions of items. For instance, searching for a specific book title might use a linear search if the database isn't perfectly ordered, while filtering by price range might use a more optimized, sorted approach.

Assessment Ideas

Quick Check

Provide students with a small, unsorted list of numbers and a target number. Ask them to manually trace the steps of a linear search, writing down each comparison made. Then, ask them to explain why binary search would not work on this specific list.

Discussion Prompt

Pose the following scenario: 'You have a list of 1000 student IDs and need to find a specific ID. Would you prefer to use linear search or binary search? Justify your answer by explaining the characteristics of the data and the algorithms.'

Exit Ticket

On an index card, have students write down one key difference between linear and binary search. Then, ask them to provide one example of when they would choose linear search over binary search.

Frequently Asked Questions

What is the main difference between linear and binary search?

Linear search scans every element sequentially, working on unsorted lists but scaling poorly at O(n). Binary search requires sorted data, divides the interval in half each step for O(log n) efficiency. Grade 10 students compare by counting steps on lists of 16, 32 items to see binary's advantage grow with size. Use cases: linear for small/unsorted, binary for large/sorted like dictionaries.

When should you use binary search over linear?

Choose binary for sorted, large lists like databases or phone books where log n steps save time. Avoid on unsorted data; sort first if beneficial. Students analyze by testing both on expanding arrays, noting binary wins past 20-30 elements typically. Curriculum ties this to real programs optimizing searches.

How can active learning help students understand searching algorithms?

Active methods like coding pairs, card simulations, and timed races make efficiency tangible. Students see linear steps balloon while binary stays low, internalizing via own data. Group debates on results correct errors, build choice skills. This beats lectures, as hands-on debugging and visualization stick longer per research on CS education.

How to teach efficiency of linear vs binary search in grade 10?

Start with unplugged card sorts to demo steps without code. Move to pair programming tests on lists doubling in size, graphing comparisons. Use visuals like binary trees. Aligns to Ontario standards CS.HS.A.3, A.4 by having students construct, compare algorithms. End with scenarios choosing best fit.