Programming 101 chevron_right Linear Search and Introduction to Algorithm Efficiency

Linear Search and Introduction to Algorithm Efficiency

calendar_today schedule 6 min read

Learning Objectives: By the end of this lesson, you will be able to:

  • Explain and implement the linear search algorithm in pseudocode
  • Analyze best, worst, and average case scenarios for linear search
  • Understand the basics of algorithm efficiency and why it matters

1. Welcome and Introduction (5 minutes)

Icebreaker Activity

Have you ever searched for a specific item in a messy drawer or a name in a long list? How did you do it? Did you have a strategy, or did you just check one by one?

Lesson Overview

  • Duration: 60–90 minutes
  • Prerequisites: Completion of Days 1–7 lessons (especially loops and lists)
  • Materials Needed: Pen and paper or a text editor for writing pseudocode

2. Learning Objectives and Session Outline (5 minutes)

What We’ll Cover Today:

  1. Review of searching and iteration
  2. The linear search algorithm: how and when to use it
  3. Best, worst, and average case analysis
  4. Introduction to algorithm efficiency
  5. Hands-on practice and exercises

Success Criteria:

By the end of this session, you should be able to write, trace, and analyze a linear search algorithm in pseudocode.

3. Foundation Knowledge (15-20 minutes)

Core Concepts

Linear search is a simple algorithm for finding a specific item in a list or array. You start at the beginning and check each item one by one until you find the target or reach the end.

Real-World Analogy: Looking for a friend’s name in a guest list by reading each name in order.

Why This Matters: Linear search is the foundation for understanding more advanced search algorithms and efficiency.

Best, Worst, and Average Case

  • Best Case: The item is the first in the list (1 comparison)
  • Worst Case: The item is the last in the list or not present at all (N comparisons)
  • Average Case: On average, you check about half the items

Introduction to Efficiency

Algorithm efficiency is about how much time (or steps) an algorithm takes as the input grows. For large lists, a slow algorithm can make a big difference!

Key Terminology

  • Linear Search: Checking each item in order
  • Efficiency: How quickly an algorithm solves a problem
  • Best/Worst/Average Case: Scenarios for how many steps an algorithm might take

4. Detailed Explanation and Examples (25-30 minutes)

Linear search is easy to implement and works on any list, sorted or unsorted. However, it can be slow for very large lists.

Practical Applications

  • Finding a contact in your phone
  • Looking for a specific product in a small inventory
  • Checking attendance in a class list

Common Misconceptions

  1. Misconception: Linear search is always fast enough. Reality: For very large lists, it can be slow compared to other algorithms.
  2. Misconception: You need a sorted list for linear search. Reality: Linear search works on any list, sorted or not.

5. Live Coding Demonstration (20-25 minutes)

Example 1: Linear Search in Pseudocode

FUNCTION linearSearch(listToSearch, itemToFind)
  SET found TO FALSE
  SET currentIndex TO 0
  WHILE currentIndex < LENGTH(listToSearch) AND found IS FALSE DO
    IF listToSearch[currentIndex] == itemToFind THEN
      SET found TO TRUE
      // Optional: STORE position = currentIndex
    ELSE
      INCREMENT currentIndex
    ENDIF
  ENDWHILE
  IF found IS TRUE THEN
    // Optional: RETURN position
    RETURN TRUE // Or "Found"
  ELSE
    RETURN FALSE // Or "Not Found"
  ENDIF
ENDFUNCTION

Explanation:

  • The loop checks each item in order
  • Stops early if the item is found
  • Returns TRUE or FALSE (or the position)
  • List: [10, 50, 30, 70, 20], Item to find: 30
  • Step through each index, showing comparisons and updates to found and currentIndex
  • Try with an item not in the list (e.g., 45)

Example 3: Best, Worst, and Average Case

  • Best case: Item is at index 0 (1 comparison)
  • Worst case: Item is at the last index or not present (N comparisons)
  • Average case: About N/2 comparisons

Debugging Demonstration

Common mistake: Forgetting to increment the index or check the loop condition correctly.

// Incorrect
WHILE currentIndex < LENGTH(listToSearch) DO
  IF listToSearch[currentIndex] == itemToFind THEN
    RETURN TRUE
  ENDIF
  // Missing increment!
ENDWHILE

// Corrected version
WHILE currentIndex < LENGTH(listToSearch) DO
  IF listToSearch[currentIndex] == itemToFind THEN
    RETURN TRUE
  ENDIF
  INCREMENT currentIndex
ENDWHILE
RETURN FALSE

6. Hands-On Practice (20-30 minutes)

Exercise 1: Basic Practice (10 minutes)

Objective: Write pseudocode for linear search that returns the index of the found item, or -1 if not found.

Starter Code:

FUNCTION linearSearch(listToSearch, itemToFind)
  // Your steps here
ENDFUNCTION

Solution:

FUNCTION linearSearch(listToSearch, itemToFind)
  FOR i FROM 0 TO LENGTH(listToSearch) - 1 DO
    IF listToSearch[i] == itemToFind THEN
      RETURN i
    ENDIF
  ENDFOR
  RETURN -1
ENDFUNCTION

Exercise 2: Intermediate Challenge (10 minutes)

Objective: Analyze the number of comparisons made in best, worst, and average cases for a list of 10 items.

Requirements:

  • Write out the number of comparisons for each scenario
  • Explain why efficiency matters for large lists

Exercise 3: Creative Application (10 minutes)

Objective: Write pseudocode for searching for a student’s name in a class list and outputting their seat number (index + 1), or a message if not found.

Extension Ideas:

  • Modify the algorithm to count how many times an item appears in the list
  • Compare linear search to searching in a sorted list with a different algorithm (preview for next lesson)

7. Common Pitfalls and Troubleshooting (10 minutes)

Frequent Mistakes

  1. Problem: Infinite loops Cause: Not incrementing the index or incorrect loop condition Solution: Always update the index and check your loop boundaries
  2. Problem: Not handling the case where the item is not found Cause: Only returning when found Solution: Return a value (like -1 or FALSE) if the loop finishes without finding the item

Debugging Tips

  • Trace your algorithm with sample data
  • Print or track the index and comparisons at each step
  • Test with items at the start, end, and not in the list

8. Best Practices and Professional Tips (5 minutes)

Industry Standards

  • Use clear, consistent loop and condition structures
  • Always handle all possible outcomes (found/not found)
  • Analyze efficiency for large data sets

Next Steps in Your Learning Journey

  • Learn about more efficient search algorithms (e.g., binary search)
  • Practice analyzing and comparing algorithm efficiency
  • Try implementing linear search in a programming language

9. Summary and Review (5 minutes)

Key Takeaways

  1. Linear search checks each item in order until found or the end is reached
  2. Efficiency matters for large lists—linear search can be slow
  3. Always handle all possible cases and test your logic

Quick Review Questions

  1. What is the best case for linear search?
  2. How many comparisons in the worst case for a list of N items?
  3. Why is efficiency important in algorithms?

For Instructors

Teaching Tips

  • Use real-world search examples (finding a name, item, etc.)
  • Encourage students to trace and count comparisons
  • Discuss why efficiency matters as data grows

Assessment Ideas

  • Have students write and trace linear search for different cases
  • Peer review: students check each other’s logic and efficiency analysis
  • Short quiz on linear search and efficiency

Adaptation Notes

  • For advanced students, introduce binary search and compare
  • For online delivery, use interactive tracing tools
  • Adjust timing based on student engagement and questions