🔍 Day 2: The Front Office

AP CSA · 4.14 — Linear Search Algorithms

The office texts: “Is student ID 40881 checked in?” Today’s data has no structure to exploit — just a flat, unsorted roster. No shortcuts hide in the order, because there is no order.

The idea to hold onto: linear search checks every element, one at a time, in sequence, until it finds a match or runs out of list. It’s the honest algorithm — no shortcuts, no guessing, works on any list at all. That generality is exactly why it can’t be fast: every trick that beats it (binary search, next lesson) demands sorted data first in return.

You’ll leave able to: search for a match and return its location, compare primitives vs. objects correctly, search by condition instead of exact equality, respect a partially-filled array’s true size, and reason about best/worst case.

Same setup as last time (IJava kernel, or paste into your IDE) — // TODO is your blank, <details> hides a hint + solution.

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[] studentIDs = {40217, 40593, 40108, 40772, 40364, 40881, 40255, 40940, 40033, 40108, 40699, 40128};
int[] quizScores = {87, 54, 92, 71, 88, 46, 79, 95, 62, 83, 58, 90};
System.out.println("Roster loaded: " + names.length + " students.");

Chapter 1 — No Shortcuts Allowed

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

-1 isn’t a real index, so it’s a safe “not found” sentinel — same trick as -1 for an empty seat yesterday.

Task 1: write indexOfID(ids, targetID) — int compares correctly with ==. Task 2: write indexOfName(roster, targetName) — but String is an object, and == checks “same object in memory,” not “same text.” Use .equals() instead, or you’ll get bugs that look correct until they mysteriously aren’t.

public static int indexOfID(int[] ids, int targetID) {
    for (int i = 0; i < ids.length; i++) {
        if (/* TODO */) return i;
    }
    return -1;
}

public static int indexOfName(String[] roster, String targetName) {
    for (int i = 0; i < roster.length; i++) {
        if (/* TODO: correct comparison for objects */) return i;
    }
    return -1;
}

System.out.println(indexOfID(studentIDs, 40881));       // real index
System.out.println(indexOfID(studentIDs, 99999));       // -1
System.out.println(indexOfName(names, "Marcus Webb"));  // real index
✅ Hint + solution ```java if (ids[i] == targetID) return i; // primitives: == if (roster[i].equals(targetName)) return i; // objects: .equals() ``` `indexOfID(studentIDs, 40881)` → `5` (1 comparison to find it if it were first — best case is O(1)). `indexOfID(studentIDs, 99999)` → `-1` after all 12 comparisons — **"not found" is always the worst case**, since you can't prove something's absent without checking everything. That's O(n) worst-case, and it's the entire reason a sorted-data shortcut (binary search) is worth learning next. Rule that never fails: primitives use `==`. Anything capitalized (`String`, objects in general) uses `.equals()`.

Chapter 2 — Search Doesn’t Mean “Equals”

“Who’s the first student with a failing quiz score?” No single target value — you’re searching for the first element matching a condition. Same skeleton, different if.

Task: write indexOfFirstBelow(scores, threshold) — first index where scores[i] < threshold, or -1.

public static int indexOfFirstBelow(int[] scores, int threshold) {
    for (int i = 0; i < scores.length; i++) {
        if (/* TODO */) return i;
    }
    return -1;
}
int idx = indexOfFirstBelow(quizScores, 60);
System.out.println(names[idx] + " scored " + quizScores[idx]);
✅ Hint + solution ```java if (scores[i] < threshold) return i; ``` Returns index `1` (Diego Ruiz, 54) — the *first* failing score, even though Priya Nair (index 5, 46) is *lower*. "First match" and "most extreme value" (yesterday's capstone pattern) are different questions that both compile without complaint — confusing them answers a question nobody asked.

Chapter 3 — The Sign-In Sheet (partially filled arrays)

An array’s .length is its capacity, not necessarily how much is actually in use. A 15-seat sign-in sheet with only 8 real check-ins has 7 slots quietly holding Java’s default 0 — not data. Loop to the logical size, never blindly to .length, whenever the two might differ. This exact array-vs-size gap is a near-guaranteed exam trap.

Task: write isSignedIn(sheet, numSignedIn, targetID).

int[] signInSheet = new int[15];
int numSignedIn = 8;
int[] realIDs = {40217, 40593, 40108, 40772, 40364, 40881, 40255, 40940};
for (int i = 0; i < realIDs.length; i++) signInSheet[i] = realIDs[i];
// signInSheet[8..14] are still just 0 — nobody's there yet.

public static boolean isSignedIn(int[] sheet, int numSignedIn, int targetID) {
    for (int i = 0; i < /* TODO: the CORRECT bound */; i++) {
        if (sheet[i] == targetID) return true;
    }
    return false;
}
System.out.println(isSignedIn(signInSheet, numSignedIn, 40940));  // true
System.out.println(isSignedIn(signInSheet, numSignedIn, 0));      // false — 0 is unused space, not a real ID
✅ Hint + solution ```java for (int i = 0; i < numSignedIn; i++) { ... } ``` Loop to `numSignedIn` (8), never `sheet.length` (15). Swap it and search for `0` — you'll get `true`, because slot 8 really does hold `0`, Java's default filler mistaken for real data. The exam often states this explicitly: *"arr has size meaningful elements, though arr.length may be larger."*

Chapter 4 — When You Don’t Stop at the First One

“Give me every failing student.” Stopping early here is now wrong — you need all of them, so drop the early return entirely.

Task: write indexesBelow(scores, threshold), returning an ArrayList<Integer> of every qualifying index.

import java.util.ArrayList;

public static ArrayList<Integer> indexesBelow(int[] scores, int threshold) {
    ArrayList<Integer> matches = new ArrayList<>();
    for (int i = 0; i < scores.length; i++) {
        if (scores[i] < threshold) {
            /* TODO: record it, don't return — more might be coming */
        }
    }
    return matches;
}
for (int i : indexesBelow(quizScores, 60)) System.out.println(names[i] + ": " + quizScores[i]);
✅ Hint + solution ```java matches.add(i); ``` Expect three: Diego Ruiz (54), Priya Nair (46), Marcus Webb (58). No early `return` inside the `if` — that's the *entire* structural difference between "find the first match" and "find every match." Adding one back here would silently cap the list at one item.

Capstone — The Duplicate ID Detector

IT flagged a possible duplicate student ID. No single target — you need to compare every ID against every other ID: a search nested inside a loop.

Task: write findDuplicateIDs, printing every duplicate pair found.

public static void findDuplicateIDs(int[] ids, String[] roster) {
    for (int i = 0; i < ids.length; i++) {
        for (int j = /* TODO: where should j start, and why? */; j < ids.length; j++) {
            if (/* TODO */) {
                System.out.println("Duplicate " + ids[i] + " at " + i + " & " + j
                        + " (" + roster[i] + " & " + roster[j] + ")");
            }
        }
    }
}
findDuplicateIDs(studentIDs, names);
✅ Hint + solution ```java for (int j = i + 1; j < ids.length; j++) { if (ids[i] == ids[j]) { ... } } ``` `j` starts at `i + 1` so you never compare a student to themselves or report the same pair twice. This surfaces **ID 40108 at indices 2 & 9** (Aaliyah Brooks & Ines Delgado). Notice the cost: roughly `12 × 12` comparisons — a perfectly good O(n) search, nested, quietly becomes **O(n²)**. Spotting "a search inside a loop over the whole list" as a red flag is a real, transferable skill.

🎯 Exam-Ready Checklist

  • == for primitives, .equals() for objects
  • Early return when you want the first/any match; no early return when you need every match
  • -1/false returned only after the loop finishes naturally
  • Loop bound uses logical size, not a blind .length, whenever they might differ
  • Method signature matches exactly what’s asked

Reflect: every method here shares one skeleton — a loop, a condition, and a decision about when to return. What’s your one-sentence rule for knowing which shape a problem wants? Next up: what happens to all of this the moment the data is guaranteed sorted.

📚 References