Basic Search Algorithms: Linear Search

Active learning helps students grasp linear search because it is a hands-on process where they physically follow each step. When students search through lists themselves, they experience firsthand how the algorithm works and why it matters.

• Class 11
• Computer Science
• 4 activities
• 10 min–25 min

Learning Objectives

1. Demonstrate the step-by-step execution of a linear search algorithm with a given list and target value.
2. Calculate the number of comparisons for best-case, worst-case, and average-case scenarios for a linear search.
3. Compare the efficiency of linear search against other potential search methods for different data sizes and states.
4. Evaluate the suitability of linear search for specific problem contexts, justifying the choice based on efficiency analysis.

Problem-Based Learning

⏱ 15 min·Individual

Manual List Search

Students receive printed lists of numbers or names. They perform linear searches for given targets, noting comparisons made. Discuss findings in class.

Prepare & details

Explain the step-by-step process of a linear search.

Facilitation Tip: During Manual List Search, give students physical index cards with numbers so they can physically move and compare each one.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Problem-Based Learning

⏱ 25 min·Pairs

Pair Coding Challenge

Pairs write Python code for linear search on sample lists. Test with best, worst, average cases. Share code and results.

Prepare & details

Analyze the best-case, worst-case, and average-case scenarios for linear search.

Facilitation Tip: For Pair Coding Challenge, pair students with different coding speeds so they can discuss and debug together.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Problem-Based Learning

⏱ 20 min·Small Groups

Efficiency Race

Small groups time manual searches on lists of increasing sizes. Graph results to visualise growth in comparisons.

Prepare & details

Predict when a linear search might be an acceptable or unacceptable solution.

Facilitation Tip: In Efficiency Race, keep the list sizes small enough for quick calculations but large enough to show differences.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Problem-Based Learning

⏱ 10 min·Whole Class

Real-World Hunt

Whole class searches for items in a simulated phonebook or dictionary page using linear method. Compare with random access.

Prepare & details

Explain the step-by-step process of a linear search.

Facilitation Tip: For Real-World Hunt, allow students to use real objects like library books or classroom items to make the activity tangible.

Setup: Standard classroom with movable furniture arranged for groups of 5 to 6; if furniture is fixed, groups work within rows using a designated recorder. A blackboard or whiteboard for capturing the whole-class 'need-to-know' list is essential.

Materials: Printed problem scenario cards (one per group), Structured analysis templates: 'What we know / What we need to find out / Our hypothesis', Role cards (recorder, researcher, presenter, timekeeper), Access to NCERT textbooks and any supplementary reference materials, Individual reflection sheets or exit slips with a board-exam-style application question

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

Teaching This Topic

Teach linear search by having students trace the process with their fingers on paper before writing code. Avoid starting with sorted lists; let them experience the raw simplicity of checking each element. Research shows that physical movement and peer discussion solidify understanding better than abstract explanations.

What to Expect

By the end, students will confidently trace linear search on unsorted lists, compare best and worst cases, and explain when this algorithm is practical. They will also articulate why sorting is unnecessary for this method.

Watch Out for These Misconceptions

Common Misconception

During Manual List Search, watch for students who skip ahead or assume the list is sorted.

What to Teach Instead

Have them write down each comparison step by step and ask them to explain why the order does not matter for this algorithm.

Common Misconception

During Efficiency Race, students may think linear search is always slow.

What to Teach Instead

Ask them to calculate the exact number of comparisons for their lists and compare results to see when it is efficient.

Common Misconception

During Real-World Hunt, students might think linear search works only for numbers.

What to Teach Instead

Have them list the items they found and explain how the same steps apply to names, objects, or any unsorted data.

Assessment Ideas

Quick Check

After Manual List Search, ask students to write down each comparison they made on a small unsorted list, the number of steps taken, and the final position of the target.

Discussion Prompt

During Efficiency Race, ask: 'For a list of 1000 roll numbers, would linear search be a good choice? Why or why not?' Listen for reasoning about time, need for sorting, and comparison counts.

Exit Ticket

After Real-World Hunt, ask students to define 'worst-case scenario' in their own words and give an example list and target that would require checking every element.

Extensions & Scaffolding

• Challenge: Ask students to create a modified linear search that counts how many times a target appears in a list.
• Scaffolding: Provide partially completed step-by-step tables for students to fill in during Manual List Search.
• Deeper exploration: Have students compare linear search with binary search on the same unsorted list to highlight why sorting matters for some algorithms.

Key Vocabulary

Linear Search	A sequential search algorithm that checks each element in a list one by one until the target element is found or the list ends.
Target Element	The specific value or item that the search algorithm is trying to locate within a dataset.
Time Complexity	A measure of how the runtime of an algorithm grows as the input size increases, often expressed using Big O notation.
Best-Case Scenario	The input arrangement that allows the algorithm to complete in the minimum possible number of operations.
Worst-Case Scenario	The input arrangement that requires the maximum number of operations for the algorithm to complete.