Computing · JC 1 · Algorithms and Computational Thinking · Semester 1

Searching Algorithms: Linear and Binary Search

Detailed study of standard searching algorithms, including their implementation and efficiency.

• MOE Syllabus Outcomes
• MOE: Algorithms and Computational Thinking - JC1

About This Topic

Searching algorithms form a core part of computational thinking in JC1 Computing. Students examine linear search, which sequentially checks each element in a list until the target is found, and binary search, which requires sorted data and halves the search space at each step. They implement both algorithms in code, measure their performance on datasets of varying sizes, and analyze time complexity using Big O notation: O(n) for linear search and O(log n) for binary search.

This topic connects to broader algorithmic efficiency and data structures. Students compare runtimes on sorted versus unsorted data, predict outcomes for large datasets, and justify choices, such as preferring linear search for small, unsorted lists or frequent insertions. These activities develop problem-solving skills essential for H2 Computing syllabus standards.

Active learning benefits this topic greatly. When students code, trace steps on paper, or simulate searches with physical cards, they experience efficiency differences firsthand. Group predictions followed by timed executions reveal patterns that lectures alone cannot match, fostering deeper understanding and retention.

Key Questions

1. Compare the efficiency of linear search versus binary search for sorted data.
2. Predict the performance of a linear search on a very large, unsorted dataset.
3. Justify when a linear search might be preferred over a binary search.

Learning Objectives

• Compare the time complexity of linear search and binary search algorithms using Big O notation.
• Implement both linear and binary search algorithms in a programming language.
• Analyze the performance of linear search on unsorted datasets of varying sizes.
• Justify the selection of linear search over binary search for specific data conditions.
• Evaluate the efficiency of binary search on sorted datasets of varying sizes.

Before You Start

Introduction to Programming Constructs (Variables, Data Types, Loops, Conditionals)

Why: Students need a foundational understanding of programming to implement and trace the algorithms.

Arrays and Lists

Why: Both algorithms operate on sequential data structures like arrays or lists, so familiarity is essential.

Key Vocabulary

Linear Search	A sequential search algorithm that checks each element of a list until the target value is found or the list ends.
Binary Search	An efficient search algorithm that repeatedly divides the search interval in half, requiring the data to be sorted first.
Time Complexity	A measure of the amount of time an algorithm takes to run as a function of the length 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.

Watch Out for These Misconceptions

Common Misconception

Binary search works on unsorted data.

What to Teach Instead

Binary search assumes sorted input; unsorted data leads to incorrect results. Hands-on card games let students test both cases, observe failures, and reinforce the sorting prerequisite through trial and peer correction.

Common Misconception

Linear search is always slower than binary search.

What to Teach Instead

Linear search suits small or unsorted lists where sorting overhead outweighs benefits. Timed coding challenges in pairs help students measure this, building intuition for real-world trade-offs via data they generate.

Common Misconception

Binary search halves the list exactly every time.

What to Teach Instead

It halves the remaining interval, but uneven splits occur based on target position. Tracing worksheets with group discussions clarify variable step counts, preventing over-simplification.

Active Learning Ideas

Pairs Coding Challenge: Implement and Time Searches

Pairs write linear and binary search functions in Python. They test on lists of 10, 100, and 1000 elements, both sorted and unsorted. Record average runtimes over 10 trials and graph results.

45 min·Pairs

Small Groups Game: Binary Search Cards

Provide sorted number cards to groups. Students take turns searching for a target using binary search rules, timing each search. Discuss why it succeeds only on sorted sets and compare to linear attempts on shuffled cards.

30 min·Small Groups

Whole Class Demo: Prediction Relay

Project a large sorted list. Students predict steps for binary search and shout halves. Teacher codes live, revealing actual steps. Class votes on linear search steps for contrast, then runs benchmarks.

35 min·Whole Class

Individual Tracing: Step-by-Step Analysis

Students trace linear and binary searches on provided arrays, marking comparisons and divisions. They calculate worst-case steps and identify pivot choices in binary search.

20 min·Individual

Real-World Connections

• A librarian uses linear search to find a specific book on a shelf when the catalog is not immediately accessible or the shelf order is not strictly alphabetical.
• Online retail platforms like Amazon employ binary search (or variations) to quickly find products within a sorted catalog, enabling rapid search results for millions of items.
• Database systems use binary search principles within indexed tables to retrieve specific records efficiently, a critical function for applications from banking to social media.

Assessment Ideas

Quick Check

Provide students with a small, sorted list of numbers and a target value. Ask them to trace the steps of a binary search on paper, indicating the search interval at each step. Then, ask them to write the Big O time complexity for binary search.

Discussion Prompt

Pose the scenario: 'You have a list of 10,000 customer IDs, unsorted. You need to find a specific ID. Which search algorithm would you choose and why? What if the list was sorted?' Facilitate a class discussion comparing their choices and justifications.

Exit Ticket

On an index card, ask students to write down one situation where linear search is a reasonable choice despite binary search's efficiency. They should also briefly explain why.

Frequently Asked Questions

How do linear and binary search compare in efficiency?

Linear search checks every element, leading to O(n) time, poor for large lists. Binary search on sorted data uses O(log n) by halving intervals, ideal for big datasets. Students benchmark both in code to see linear falter on 10,000 items while binary excels, grasping why preprocessing matters.

When should teachers prefer linear search over binary?

Use linear for small lists, unsorted data, or when sorting costs time. It avoids preprocessing overhead. Classroom activities like searching short word lists show linear's simplicity wins for quick, infrequent lookups, aligning with key questions on justification.

How can active learning help students understand searching algorithms?

Active approaches like card simulations and paired coding make abstract Big O tangible. Students predict, execute, and compare runtimes, discovering efficiency gaps through data they collect. Group discussions after traces correct misconceptions, boosting engagement and long-term recall over passive notes.

What tools help visualize binary search steps?

Python with matplotlib for runtime graphs or online visualizers like VisuAlgo. In class, live coding demos with pauses for predictions engage students. These tools, paired with physical props, solidify the halving process and pivot selection for JC1 learners.