4.14 Linear Search Algorithms

1. Reference Guide

Key Topics

Term	Definition	Example
Linear search	Check each element in order until a match is found or the list ends.	`for (int i = 0; i < arr.length; i++)`
Sentinel	A value that cannot be a real index, returned for “not found”.	`return -1;`
`==` vs `.equals()`	`==` for primitives; `.equals()` for objects such as `String`.	`roster[i].equals(name)`
Logical size	How many slots hold real data, which may be less than `.length`.	`i < numSignedIn`

Linear search works on any list, sorted or not. That generality is why it can’t be fast: the best case is O(1) and the worst case is O(n).
Searching by a condition uses the same loop as searching by equality. Only the if changes.
“First match” and “most extreme value” are different questions, and both compile.

Picking an Algorithm

First match → return i inside the if, and return -1 only after the loop
Every match → collect into an ArrayList<Integer> and drop the early return
Partially filled array → loop to the logical size, never a blind .length
Compare every pair → nested loop with j starting at i + 1; it is O(n²)

2. LxD Cycle Process

Empathize: Students know a loop with an if, but mix up == and .equals(), return too early when they need every match, and loop to .length on a partly filled array. Each of these compiles and quietly gives the wrong answer.

Define:

POV: CSA students need to see every linear search as one skeleton: a loop, a condition, and a decision about when to return.
Learning Goal: Students will search for a value or a condition, choose between the first match and every match, compare objects correctly, and respect a partially filled array’s size.

Ideate:

HMW Question: How might we show each silent bug next to its fix so students see the wrong answer before they learn the rule?
Activity: Compare == and .equals() in a runner, trace loops in the MCQ, then write lastIndexOf and countBelow.

Prototype:

A reference guide, three runnable Java examples, a personalized popcorn hack, an MCQ knowledge check, and a scaffolded grade rubric.
Excellence means explaining when to stop early, why .equals() is needed, and why the loop stops at the logical size.

Test:

Ask peers in peer review to complete the practice without additional explanation.
Observe whether peers loop to size and use .equals() without being told.
On submission, collect evidence from runner output, MCQ results, AI grading and student explanations.
After teaching, grading and analysis, come back and revise lesson to complete teaching cycle for continuous improvement.

3. College Board Requirements

AP CSA Unit 4, Topic 4.14 Searching Algorithms (Linear Search). Paraphrased from the course and exam description (College Board, 2025, p. 125):

Linear (sequential) search checks each element in order until it finds the target or reaches the end of the list.
Linear search can be applied to an array or an ArrayList, and it can look for a match by value or by a condition.
Search algorithms can be written to find the first match or to find every match.

4. Lesson Plan

Learning Objective: Write linear searches that return the index of a match, search by condition, collect every match, and respect a partially filled array’s size.

Success Criteria: You can explain why == fails on String objects and why the loop bound is the logical size, not .length.

Tech Talk (5 minutes)

The Front Office. The office texts: “Is student ID 40881 checked in?” The roster is flat and unsorted, so no shortcut hides in the order. Linear search is the honest algorithm: it checks every element, one at a time, until it finds a match or runs out of list.

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;   // found it, so stop immediately
}
return -1;                            // walked everything, it isn't here

5. Code Examples

A. Comparing names. The NameSearch class searches the same roster with `.equals()` and with `==`

Common starting mistake:


if (roster[i] == targetName)        // same object in memory?
if (roster[i].equals(targetName))   // same text?

Terminology:

int is a primitive, so == compares values. String is an object, so == compares references. Anything capitalized uses .equals().

Code Runner Challenge

Predict both results before running, then change new String("Marcus Webb") to just "Marcus Webb"

View IPYNB Source

// CODE_RUNNER: Predict both results before running, then change new String("Marcus Webb") to just "Marcus Webb"
// == vs. .equals() when searching names
public class NameSearch {
    public static int indexWithEquals(String[] roster, String target) {
        for (int i = 0; i < roster.length; i++) {
            if (roster[i].equals(target)) return i;
        }
        return -1;
    }

    public static int indexWithDoubleEquals(String[] roster, String target) {
        for (int i = 0; i < roster.length; i++) {
            if (roster[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] names = {"Maya Chen", "Diego Ruiz", "Marcus Webb"};
        String typed = new String("Marcus Webb");   // same text, different object

        System.out.println(".equals: " + indexWithEquals(names, typed));
        System.out.println("==:      " + indexWithDoubleEquals(names, typed));
    }
}

NameSearch.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

B. First match or every match. The FirstOrEvery class finds failing quiz scores two ways

Common starting mistake:


if (scores[i] < threshold) return i;        // stops at the first match
if (scores[i] < threshold) matches.add(i);  // keeps going and collects them all

Terminology:

An early return means “find the first”. No early return means “find every”. The first failing score is not the lowest one: Diego Ruiz (54) comes before Priya Nair (46).

Code Runner Challenge

Predict both outputs before running, then change the threshold to 50

View IPYNB Source

// CODE_RUNNER: Predict both outputs before running, then change the threshold to 50
// First match vs. every match
import java.util.ArrayList;

public class FirstOrEvery {
    public static int indexOfFirstBelow(int[] scores, int threshold) {
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] < threshold) return i;
        }
        return -1;
    }

    public static ArrayList<Integer> indexesBelow(int[] scores, int threshold) {
        ArrayList<Integer> matches = new ArrayList<Integer>();
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] < threshold) matches.add(i);
        }
        return matches;
    }

    public static void main(String[] args) {
        String[] names = {"Maya Chen", "Diego Ruiz", "Aaliyah Brooks", "Sam Okafor", "Jordan Blake",
                          "Priya Nair", "Liam Carter", "Zoe Fischer", "Noah Kim", "Ines Delgado",
                          "Marcus Webb", "Grace Liu"};
        int[] quizScores = {87, 54, 92, 71, 88, 46, 79, 95, 62, 83, 58, 90};

        int first = indexOfFirstBelow(quizScores, 60);
        System.out.println("first: " + names[first] + " (" + quizScores[first] + ")");

        System.out.println("every:");
        for (int i : indexesBelow(quizScores, 60)) {
            System.out.println("  " + names[i] + " (" + quizScores[i] + ")");
        }
    }
}

FirstOrEvery.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Common starting mistake:


for (int i = 0; i < sheet.length; i++)         // includes the unused slots
for (int i = 0; i < numSignedIn; i++)          // only real check-ins

Terminology:

.length is the capacity. The logical size is how many slots hold real data. Unused slots hold Java’s default 0, which a search can mistake for a real ID.

Code Runner Challenge

Predict both lines before running, then also search for 40940 in both

View IPYNB Source

// CODE_RUNNER: Predict both lines before running, then also search for 40940 in both
// Searching to .length vs. the logical size
public class SignInSheet {
    public static boolean searchToLength(int[] sheet, int target) {
        for (int i = 0; i < sheet.length; i++) {
            if (sheet[i] == target) return true;
        }
        return false;
    }

    public static boolean searchToSize(int[] sheet, int numSignedIn, int target) {
        for (int i = 0; i < numSignedIn; i++) {
            if (sheet[i] == target) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] sheet = new int[15];
        int numSignedIn = 8;
        int[] realIDs = {40217, 40593, 40108, 40772, 40364, 40881, 40255, 40940};
        for (int i = 0; i < realIDs.length; i++) sheet[i] = realIDs[i];

        System.out.println("to length, ID 0: " + searchToLength(sheet, 0));
        System.out.println("to size,   ID 0: " + searchToSize(sheet, numSignedIn, 0));
    }
}

SignInSheet.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

6. Hacks & Practice Tasks

Prepare your submission IPYNB

Create a new notebook in your portfolio homework area: _notebooks/homework.
Add one raw cell at the top with the frontmatter:

---
layout: post
codemirror: true
title: Linear Search Algorithms HW
categories: [Java]
lesson_language: Java
lesson_topic: Linear Search Algorithms HW
lesson_part: interactive
lesson_type: lesson
permalink: /csa/unit_04/4_14-hw
author: yourGithubID
---

Add code cells for the Popcorn Hack and the Homework Hack. Make sure every cell runs with visible output.
Submit the link to your published page at the bottom of this page, and paste this in the description box:

Lesson: CSA 4.14 Linear Search Algorithms
MCQ 4.14: <paste the copied result line, such as 3/4 | answers: C,B,C,B>
Popcorn: five values of my own, first day at 120+ and a not-found index printed (yes/no)
Homework: lastIndexOf outputs = <outputs>
Homework: countBelow output = <output>

Submission Safety Rules (Read First)

One class per cell, ending with ClassName.main(null);.
Run each cell and leave the output showing.
Use your own values, not the sample answer.
Include your MCQ score.
Use ## headings or smaller.

Popcorn Hack (In-Class)

2-minute challenge: analyze five days of your own study time, then run the cell.

Store the minutes in an int[]
Find the index of the first day with at least 120 minutes
Search for a day of exactly 50 minutes and print what comes back

Replace the sample values with your own.

Code Runner Challenge

Replace the sample values with your own, then run it

View IPYNB Source

// CODE_RUNNER: Replace the sample values with your own, then run it
// Practice #1 - Try it yourself first!
public class MyStudyLog {
    public static int indexOfFirstAtLeast(int[] arr, int min) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= min) return i;
        }
        return -1;
    }

    public static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        // Try writing your own code here first!

        // Sample answer:
        int[] minutes = {95, 140, 80, 180, 120};

        System.out.println("First day at 120+: index " + indexOfFirstAtLeast(minutes, 120));
        System.out.println("A day of exactly 50: index " + indexOf(minutes, 50));
    }
}

MyStudyLog.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

MCQ Check

4 questions, one at a time. Answer, check, then go to the next one. At the end, copy the score line into your submission notes.

Homework Hack

Task: Write two algorithms for a partly filled array, where only the first size slots hold real data. lastIndexOf returns the index of the last match, or -1. countBelow counts the values below a threshold.

Solution Skeleton:

Code Runner Challenge

Fill in the blanks, then run it

View IPYNB Source

// CODE_RUNNER: Fill in the blanks, then run it
public class SearchAlgorithms {
    // 1. Loop BACKWARD from size - 1 and return the first index that matches
    public static int lastIndexOf(int[] arr, int size, int target) {
        return 0;
    }

    // 2. Loop to size, not arr.length, and count the values below threshold
    public static int countBelow(int[] sheet, int size, int threshold) {
        return 0;
    }

    public static void main(String[] args) {
        int[] sheet = {72, 55, 90, 55, 61, 0, 0, 0};
        int size = 5;   // only the first 5 slots hold real data

        System.out.println(lastIndexOf(sheet, size, 55));    // expect 3
        System.out.println(lastIndexOf(sheet, size, 100));   // expect -1
        System.out.println(lastIndexOf(sheet, size, 0));     // expect -1, since 0 is unused space
        System.out.println(countBelow(sheet, size, 60));     // expect 2
    }
}

SearchAlgorithms.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Grading Plan (1 Point Total)

Part	Points	What earns the points
Popcorn	0.2	Five values of your own, with the first 120+ index and a not-found index printed, and the cell runs.
MCQ	0.2	4 correct. 0.15 for 2 or 3, 0.1 if every question was answered.
Homework: last index	0.15	`lastIndexOf` loops backward from `size - 1` and returns at the first match.
Homework: last index output	0.15	Prints `3`, `-1`, and `-1`.
Homework: count below	0.15	`countBelow` loops to `size`, not `.length`.
Homework: count below output	0.15	Prints `2`.
Total	1.0

Quick Validation Checklist

Each cell ends with ClassName.main(null); and shows output.
MCQ score in the notes.
Loops stop at the logical size.
The search for 0 returns -1.

7. Lesson Revisions

Revision Made: Rebuilt the lesson in the 4.10 layout. The chapter exercises became three runnable examples (== vs .equals(), first match vs every match, and .length vs the logical size). The duplicate ID capstone moved into the Reference Guide and the MCQ, and the homework now asks for a backward search and a count on a partly filled array.

(Add what you changed after peer review.)

8. Feedback Evidence

Feedback Received: (Add after peer review: what peers did, where they got stuck, and what you changed because of it.)

9. References

College Board. (2025). AP Computer Science A course and exam description (Effective fall 2025). Topic 4.14 Searching Algorithms (Linear Search), p. 125.

Oracle. (n.d.). String.equals(). In Java SE 8 documentation.

Oracle. (n.d.). ArrayList. In Java SE 8 documentation.

Submit Assignment

Need to update a submission later? Open the submissions dashboard.

Create Microblog Post

Review from a phone

Reply to Post

1. Reference Guide

Key Topics

Picking an Algorithm

2. LxD Cycle Process

3. College Board Requirements

4. Lesson Plan

Tech Talk (5 minutes)

5. Code Examples

A. Comparing names. The NameSearch class searches the same roster with .equals() and with ==

Code Runner Challenge

B. First match or every match. The FirstOrEvery class finds failing quiz scores two ways

Code Runner Challenge

C. The sign-in sheet. The SignInSheet class searches a partly filled array two ways

Code Runner Challenge

6. Hacks & Practice Tasks

Prepare your submission IPYNB

Submission Safety Rules (Read First)

Popcorn Hack (In-Class)

Code Runner Challenge

MCQ Check

Homework Hack

Code Runner Challenge

Grading Plan (1 Point Total)

Quick Validation Checklist

7. Lesson Revisions

8. Feedback Evidence

9. References

Submit Assignment

A. Comparing names. The NameSearch class searches the same roster with `.equals()` and with `==`