Teacher Guide: Searching Algorithms

Student page: Searching Algorithms IB Syllabus: B2.4.2 Estimated periods: 2 (90 min each) Prerequisites: 1D Arrays, Iteration, Selection

Contents

1. Lesson Plans
2. Differentiation
3. Answer Keys
   1. Linear Search Practice
   2. Binary Search Practice
   3. Combined Practice
4. Integration Notes
   1. Additional Resources

---

Lesson Plans

Period 1: Linear Search (90 min)

Phase	Time	Activity	Student Page Section
Warm-up	10 min	“Guess My Card” activity: shuffle a deck face-down, volunteer flips cards one by one looking for Ace of Spades. Ask: “Worst case, how many flips?”	-
Teach	20 min	Linear search algorithm: trace table on board first, then Java code. Emphasise && !found early exit and == target comparison	Key Concepts, Linear Search
Practice	25 min	Linear Search Quick Check MCQs + Trace Exercise + Code Completion from student page	Linear Search Quick Check, Trace Exercise
Practice	25 min	Linear Search Practice #1-3 (Find a Name, Count Comparisons, Last Occurrence)	Linear Search Practice
Wrap-up	10 min	Bug Spot + Output Prediction exercises. Ask: “What is the worst case for linear search? Best case?”	Spot the Bug, Output Prediction

Teaching notes:

• Do the trace table on the board BEFORE showing any code. Students who can trace can code.
• The && !found condition is a key teaching point. Show what happens without it: the loop runs unnecessarily after finding the target. With duplicates, it prints multiple times.
• String comparison: remind students to use .equals() not ==. This was covered in Strings (B2.1.2) but many students forget. The student page has a reminder box at the top.
• All code is inline in main since methods haven’t been taught yet. The pseudocode method version is shown as a preview.

Additional notes:

• For Practice #1 (Find a Name), this is the first time students apply search to Strings. Reinforce .equals().
• For Practice #3 (Last Occurrence), hint: remove the !found exit condition and always update the index. This makes students think about why early exit exists.

Period 2: Binary Search + Comparison (90 min)

Phase	Time	Activity	Student Page Section
Warm-up	10 min	“Guess My Number” 1-100: teacher demonstrates binary search live, always guessing the midpoint. At most 7 guesses.	-
Teach	25 min	Binary search: sorted prerequisite, first/last/middle logic, trace both “found” and “not found” cases on the board	Binary Search
Practice	20 min	Binary Search Quick Check MCQs + both Trace Exercises (found and not found)	Binary Search Quick Check, Trace Exercises
Practice	20 min	Binary Search Practice #1-2 (Trace on Paper, Trace Not Found) + Code Completion	Binary Search Practice
Wrap-up	15 min	Linear vs Binary comparison table from student page. Combined Quick Check MCQs. “When is the cost of sorting worthwhile?”	Linear vs Binary Search, Combined Exercises

Teaching notes:

• Binary search is harder to code than to trace. Do MULTIPLE trace examples on the board before coding. Include at least one “not found” case where first > last terminates the loop.
• The sorted array prerequisite is critical. Demonstrate binary search on an unsorted array: it silently fails (returns “not found” even when the element exists). No error is thrown, making this a dangerous bug.
• For the “Guess My Number” warm-up: after 2-3 rounds, ask “How many guesses for 1-128? 1-1024?” Students calculate 7 and 10. This leads naturally to log2.
• The first <= last loop condition is a common source of confusion. Use the “not found” trace to show exactly when first crosses last.
• .compareTo() for String binary search: mention briefly but do not dwell. The student page has a reminder box. Students will encounter this in Practice #3 (Game Inventory Search) in the Combined Exercises.

Additional notes:

• If time permits, assign Combined Practice #1 (Compare Both Searches) as an in-class extension
• Combined Practice #2 (Choose the Right Algorithm) works well as a class discussion rather than individual work
• Combined Practice #4 (Efficiency Analysis) reinforces log2 calculations: 20 comparisons for 1,000,000 elements

---

Differentiation

Supporting weaker students:

Strategy	When to use	Example
Trace template	Can’t set up trace tables	Pre-printed templates: linear search (i, arr[i], ==target?, found) and binary search (first, last, middle, arr[middle], decision)
One algorithm per day	Overwhelmed by both	Spend full Period 1 on linear search only. Move binary search entirely to Period 2
Visual number line	Can’t follow binary search boundaries	Draw a number line with first/last markers. Physically move markers after each step
Pair tracing	Struggles with independent trace	One student dictates the next step, the other fills in the trace table
Scaffold the code	Can write traces but not code	Provide the code with 1-2 blanks (like Code Completion) instead of writing from scratch

Extending stronger students:

Strategy	When to use	Example
Comparison counter	Finishes linear search early	“Add a counter to track how many comparisons were made. Run on arrays of size 10, 100, 1000. What pattern do you see?”
String binary search	After binary search code	Combined Practice #3 (Game Inventory): use .compareTo() to search String arrays
Efficiency analysis	After both algorithms	Combined Practice #4: calculate microseconds for 1,000,000 elements. “How long would each take?”
Edge case exploration	After both traces	“What happens if the array has 0 elements? 1 element? What if every element is the target?”
Algorithm timing	Extension project	Use System.nanoTime() to time both algorithms on large arrays. Graph the results
GitHub Classroom	Independent practice	Assign the Searching template for homework

---

Answer Keys

Linear Search Practice

Linear 1: Find a Name

public class FindName {
    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charlie", "Diana", "Eve"};
        String target = "Charlie";
        boolean found = false;

        for (int i = 0; i < names.length && !found; i++) {
            if (names[i].equals(target)) {
                found = true;
                System.out.println("Found at index: " + i);
            }
        }

        if (!found) {
            System.out.println("Not found");
        }
    }
}

Expected output:

Found at index: 2

Common mistakes: Using == instead of .equals() for String comparison; forgetting && !found (works but inefficient)

Marking notes: Must use .equals(). Accept solutions without && !found (still correct, just less efficient). The key check is String comparison method.

Linear 2: Count Comparisons

public class CountComparisons {
    public static void main(String[] args) {
        int[] numbers = {10, 1, 32, 41, 16, 60, 75, 82, 90, 11};
        int target = 75;
        boolean found = false;
        int comparisons = 0;

        for (int i = 0; i < numbers.length && !found; i++) {
            comparisons++;
            if (numbers[i] == target) {
                found = true;
                System.out.println("Found at index: " + i);
            }
        }

        if (!found) {
            System.out.println("Not found");
        }
        System.out.println("Comparisons: " + comparisons);
    }
}

Expected output:

Found at index: 6
Comparisons: 7

Common mistakes: Incrementing the counter inside the if block (only counts successful comparisons); placing the counter after the loop (counts iterations, not comparisons if break is used)

Marking notes: Counter must increment for every element checked, not just the match. Accept placement before or after the if statement, as long as it counts each iteration. The count should be 7 (indices 0 through 6).

Linear 3: Search for the Last Occurrence

public class LastOccurrence {
    public static void main(String[] args) {
        int[] data = {5, 12, 8, 12, 3, 12, 7};
        int target = 12;
        int lastIndex = -1;

        for (int i = 0; i < data.length; i++) {
            if (data[i] == target) {
                lastIndex = i;
            }
        }

        if (lastIndex != -1) {
            System.out.println("Last occurrence at index: " + lastIndex);
        } else {
            System.out.println("Not found");
        }
    }
}

Expected output:

Last occurrence at index: 5

Common mistakes: Using && !found (this stops at the FIRST occurrence); using break after finding a match (same problem); searching backwards and stopping at first match (correct but not the intended approach)

Marking notes: The key insight is that the loop must NOT exit early. It must check every element and keep updating lastIndex. Accept reverse-traversal solutions that use break, since they also find the last occurrence correctly. The answer is index 5.

Linear 4: Not Found Case (Trace)

Trace of linear search for 99 in {15, 33, 8, 72, 50}:

i	numbers[i]	== 99?	found
0	15	false	false
1	33	false	false
2	8	false	false
3	72	false	false
4	50	false	false

Loop ends because i reaches 5 (= numbers.length). found is still false.

Output: The number does not exist.

Marking notes: Students must show all 5 iterations. The key point is that the loop exhausts the entire array before concluding the value is not present. This is the worst case for linear search: O(n) comparisons.

Binary Search Practice

Binary 1: Trace on Paper (Search for 42)

Array: {5, 12, 18, 24, 33, 42, 56, 71} (indices 0-7)

Step	first	last	middle	sorted[middle]	Decision
1	0	7	3	24	42 > 24, search right: first = 4
2	4	7	5	42	42 == 42, Found!

Found at index: 5

Only 2 comparisons needed (linear search would have needed 6).

Marking notes: Students must show first, last, middle, the value at middle, and the decision for each step. The middle calculation is (first + last) / 2 using integer division. Accept different column labels (low/high instead of first/last).

Binary 2: Trace Not Found (Search for 25)

Array: {5, 12, 18, 24, 33, 42, 56, 71} (indices 0-7)

Step	first	last	middle	sorted[middle]	Decision
1	0	7	3	24	25 > 24, search right: first = 4
2	4	7	5	42	25 < 42, search left: last = 4
3	4	4	4	33	25 < 33, search left: last = 3

After step 3: first (4) > last (3), loop ends. Value not found.

Marking notes: The critical step is the termination: first > last means the search space is empty. Students must show all 3 steps and explain why the loop ends. Common error: forgetting step 3 and claiming “not found” after step 2.

Binary 3: Parallel Arrays

public class ParallelSearch {
    public static void main(String[] args) {
        int[] id = {1001, 1002, 1050, 1100, 1120, 1180, 1200, 1400};
        String[] name = {"Apple", "Cherry", "Peach", "Banana", "Fig", "Grape", "Olive", "Mango"};

        int target = 1120;
        int first = 0;
        int last = id.length - 1;
        boolean found = false;

        while (first <= last && !found) {
            int middle = (first + last) / 2;

            if (target == id[middle]) {
                found = true;
                System.out.println("ID " + target + " belongs to: " + name[middle]);
            } else if (target < id[middle]) {
                last = middle - 1;
            } else {
                first = middle + 1;
            }
        }

        if (!found) {
            System.out.println("ID " + target + " not found.");
        }
    }
}

Expected output:

ID 1120 belongs to: Fig

Common mistakes: Using name.length instead of id.length (both work here since they are the same length, but conceptually the search is on the ID array); searching the name array instead of the ID array; forgetting that the ID array must be sorted for binary search to work

Marking notes: The key concept is parallel arrays: the index found in one array is used to access the corresponding element in the other. The ID array is already sorted, which is required for binary search. Accept id.length or name.length since they are equal.

Binary 4: Search and Report

import java.util.Scanner;

public class SearchAndReport {
    public static void main(String[] args) {
        int[] data = {3, 8, 15, 22, 29, 36, 43, 50};

        Scanner sc = new Scanner(System.in);
        System.out.print("Enter target: ");
        int target = sc.nextInt();

        int first = 0;
        int last = data.length - 1;
        boolean found = false;
        int comparisons = 0;

        while (first <= last && !found) {
            int middle = (first + last) / 2;
            comparisons++;

            if (target == data[middle]) {
                found = true;
                System.out.println("Found at index: " + middle);
            } else if (target < data[middle]) {
                last = middle - 1;
            } else {
                first = middle + 1;
            }
        }

        if (!found) {
            System.out.println("Not found.");
        }
        System.out.println("Comparisons: " + comparisons);
    }
}

Example output (searching for 36):

Enter target: 36
Found at index: 5
Comparisons: 2

Trace for target = 36: middle=3 (22), search right; middle=5 (36), found. The loop runs exactly 2 iterations, so the counter increments twice.

Common mistakes: Not counting comparisons correctly (incrementing inside only the if block); placing the counter outside the loop

Marking notes: Accept the counter before or after the comparison checks, as long as it increments once per loop iteration. For target = 36 the answer is 2 comparisons.

Binary 5: Why Does Binary Search Fail on Unsorted Data?

Sample answer:

Consider the unsorted array {50, 10, 40, 20, 30}. Search for 10.

Step	first	last	middle	arr[middle]	Decision
1	0	4	2	40	10 < 40, search left: last = 1
2	0	1	0	50	10 < 50, search left: last = -1

Loop ends with first (0) > last (-1). Returns “not found,” even though 10 is at index 1.

Why it fails: In step 1, binary search assumes all elements to the right of middle are greater than 40 (because the array should be sorted). It eliminates indices 3 and 4. But 20 and 30 are actually less than 40. The fundamental assumption of binary search, that elements are ordered, is violated. The algorithm eliminates the wrong half of the array.

Marking notes: Students must provide a concrete example (specific array and target), show the trace, and explain which half was incorrectly eliminated and why. The explanation must reference the sorted assumption.

Combined Practice

Combined 1: Compare Both Searches

import java.util.Scanner;

public class CompareBoth {
    public static void main(String[] args) {
        // Create sorted array: 5, 10, 15, ..., 100
        int[] data = new int[20];
        for (int i = 0; i < data.length; i++) {
            data[i] = (i + 1) * 5;
        }

        Scanner sc = new Scanner(System.in);
        System.out.print("Enter target: ");
        int target = sc.nextInt();

        // Linear search
        boolean linearFound = false;
        int linearComparisons = 0;
        for (int i = 0; i < data.length && !linearFound; i++) {
            linearComparisons++;
            if (data[i] == target) {
                linearFound = true;
                System.out.println("Linear: Found at index " + i);
            }
        }
        if (!linearFound) {
            System.out.println("Linear: Not found");
        }
        System.out.println("Linear comparisons: " + linearComparisons);

        // Binary search
        boolean binaryFound = false;
        int binaryComparisons = 0;
        int first = 0;
        int last = data.length - 1;
        while (first <= last && !binaryFound) {
            int middle = (first + last) / 2;
            binaryComparisons++;
            if (target == data[middle]) {
                binaryFound = true;
                System.out.println("Binary: Found at index " + middle);
            } else if (target < data[middle]) {
                last = middle - 1;
            } else {
                first = middle + 1;
            }
        }
        if (!binaryFound) {
            System.out.println("Binary: Not found");
        }
        System.out.println("Binary comparisons: " + binaryComparisons);
    }
}

Example output (searching for 75):

Enter target: 75
Linear: Found at index 14
Linear comparisons: 15
Binary: Found at index 14
Binary comparisons: 2

Common mistakes: Reusing the same found variable for both searches (the second search would skip immediately); not resetting variables between searches; using break in one and !found in the other (inconsistent but not wrong)

Marking notes: Both searches must run independently. Accept any reasonable variable naming. The comparison counts should show that binary search uses significantly fewer comparisons. For the 20-element array, binary search needs at most 5 comparisons (log2(20) is approximately 4.3, rounded up).

Combined 2: Choose the Right Algorithm

(a) Searching a phone book for a name: Binary search. A phone book is sorted alphabetically, so binary search works. Open to the middle, decide which half based on alphabetical order, repeat. This is how people naturally use phone books.

(b) Finding a specific card in a shuffled deck: Linear search. The deck is shuffled (unsorted), so binary search cannot be used. You must check cards one by one.

(c) Looking up a word in a dictionary: Binary search. A dictionary is sorted alphabetically. Open to approximately the right section, then narrow down. This is essentially binary search.

(d) Checking if a student ID exists in an unsorted attendance list: Linear search. The list is unsorted, so binary search would produce incorrect results. You must check each entry sequentially.

Marking notes: Key assessment point: students must identify whether the data is sorted and use that to justify their choice. Answers that mention “sorted” or “unsorted” as the reason score full marks. Answers that only say “binary is faster” without mentioning the sorted requirement score partial marks.

Combined 3: Game Inventory Search

import java.util.Scanner;

public class GameInventory {
    public static void main(String[] args) {
        String[] items = {"Bow", "Dagger", "Helmet", "Potion", "Ring", "Shield", "Staff", "Sword"};

        Scanner sc = new Scanner(System.in);
        System.out.print("Search for item: ");
        String target = sc.nextLine();

        int first = 0;
        int last = items.length - 1;
        boolean found = false;

        while (first <= last && !found) {
            int middle = (first + last) / 2;
            int comparison = target.compareTo(items[middle]);

            if (comparison == 0) {
                found = true;
            } else if (comparison < 0) {
                last = middle - 1;
            } else {
                first = middle + 1;
            }
        }

        if (found) {
            System.out.println("Item found in inventory!");
        } else {
            System.out.println("Item not in inventory.");
        }
    }
}

Example output (searching for “Shield”):

Search for item: Shield
Item found in inventory!

Common mistakes: Using == instead of .compareTo() for boundary decisions; using .equals() for the less-than/greater-than check (.equals() only returns true/false, not the ordering); forgetting that .compareTo() returns negative/zero/positive, not -1/0/1 specifically; items not sorted alphabetically

Marking notes: The critical technique is .compareTo(). Students must:

1. Use .compareTo() (or .equals() for the match check combined with .compareTo() for ordering)
2. Check if the result is negative (target comes before), zero (match), or positive (target comes after)
3. Have items sorted alphabetically

Accept solutions that use .equals() for the match check and .compareTo() only for the left/right decision. Both approaches are correct.

Combined 4: Efficiency Analysis

(a) Linear search worst case: 1,000,000 comparisons. Linear search checks every element in the worst case.

(b) Binary search worst case: 20 comparisons. log2(1,000,000) is approximately 19.9, so at most 20 comparisons.

Calculation: 2^20 = 1,048,576 > 1,000,000, so 20 halvings are sufficient.

(c) Time at 1 microsecond per comparison:

• Linear search: 1,000,000 microseconds = 1 second
• Binary search: 20 microseconds = 0.00002 seconds

Binary search is 50,000 times faster in the worst case.

Marking notes: For part (b), accept 19 or 20 (depending on whether students round log2(1,000,000) up or compute the ceiling). The key insight for part (c) is the dramatic difference in real time: 1 second vs 20 microseconds. This makes the theoretical Big O difference tangible.

---

Integration Notes

Item	In Class	Homework	Link
Linear Search content + trace	Period 1 teach	-	Linear Search
Linear Search Quick Check	Period 1 practice	-	Quick Check
Linear Search Trace + Code Completion	Period 1 practice	-	Trace Exercise
Linear Search Bug Spot + Output	Period 1 wrap-up	-	Spot the Bug
Linear Practice #1-3	Period 1 practice	Complete for homework if needed	Practice
Linear Practice #4	-	Homework trace exercise	Practice
Binary Search content + traces	Period 2 teach	-	Binary Search
Binary Search Quick Check	Period 2 practice	-	Quick Check
Binary Search Trace Exercises	Period 2 practice	-	Trace Exercises
Binary Search Code Completion	Period 2 practice	-	Code Completion
Binary Practice #1-2	Period 2 practice	-	Practice
Binary Practice #3-5	-	Homework	Practice
Combined Quick Check	Period 2 wrap-up	-	Combined Check
Combined Practice #1-4	-	Extension homework	Combined Practice
GitHub Classroom	-	Due end of week	GitHub Classroom

Additional Resources

• “Guess My Card” deck for linear search warm-up (any standard playing card deck)
• “Guess My Number” 1-100 for binary search warm-up (no materials needed)
• Pre-printed trace table templates: linear search (i, arr[i], ==target?, found) and binary search (first, last, middle, arr[middle], decision)
• Comparison poster: linear O(n) vs binary O(log n) with scaling table (10, 100, 1000, 1,000,000 elements)