Activity 5.3 — Common Array Algorithms

Introduction

Activity 5.3

Using traversal to solve problems

Today's Big Idea

Most array “algorithms” are the same loop… with different logic inside.
We're learning patterns you can reuse on MC and FRQs.
Two extras for fun: swap + binary search.

Algorithm Template (the loop shape)

1
// Traversal template (the "shape" of many algorithms)
2
for (int i = 0; i < arr.length; i++)
3
{
4
    // work with arr[i]
5
}

i is the index
arr[i] is the element
Algorithms differ by what happens inside the loop

Review Patterns (Quick)

Sum/Average: accumulator (sum += arr[i])
Count: loop + if + counter (count++)
Min/Max: track best-so-far and update

Min/Max Pattern (why start at index 1?)

1
// Max pattern (start with first element)
2
int max = arr[0];
3

4
for (int i = 1; i < arr.length; i++)
5
{
6
    if (arr[i] > max)
7
    {
8
        max = arr[i];
9
    }
10
}

We initialize with arr[0] so max starts as a real value.
Then we compare the rest (starting at index 1).

Swap Algorithm (precursor to sorting)

Goal: exchange two elements without losing either value.

1
// Swap pattern (requires a temp variable)
2
int temp = arr[i];
3
arr[i] = arr[j];
4
arr[j] = temp;

temp holds one value safely
Without temp, you overwrite and lose data
This is the “move” used in many sorting methods

Linear Search (AP Required)

Idea: check every element until you find the target.

1
// Linear search: "check every element"
2
boolean found = false;
3

4
for (int i = 0; i < arr.length; i++)
5
{
6
    if (arr[i] == target)
7
    {
8
        found = true;
9
    }
10
}

Works on any array (sorted or not)
Can return a boolean or an index (often -1 if not found)

Binary Search (Enrichment / For Fun)

Requirement: array must be sorted
Instead of checking every element, we check the middle
Then we throw away half the search space
Not required for AP CSA

Binary Search Loop Skeleton

1
// Binary search (enrichment): "cut the search space"
2
int low = 0;
3
int high = arr.length - 1;
4

5
while (low <= high)
6
{
7
    int mid = (low + high) / 2;
8

9
    // compare arr[mid] to target
10
    // move low or high inward
11
}

If middle is too small → move low up
If middle is too big → move high down
If equal → found

Trace It (quick oral check)

Array: [2, 4, 7, 9, 12, 15], target = 12
mid starts at index 2 (value 7)
Is target left or right?

Success Today

You can recognize the pattern based on the goal.
You can write the code with correct braces + indentation.
You can trace what happens step-by-step.

'F' → Fullscreen

Objectives

Use array traversal to solve common problems (min/max, counting).
Use a swap algorithm to exchange two array elements.
Implement linear search and report a result (boolean and index).
Implement binary search as an optional enrichment challenge.

Activity Tasks

Create a new project named Activity5-3-ArrayAlgorithms.
Complete Tasks 1 through 3. Task 4 is optional enrichment.

Task 1: Min & Max (Review)

Track the smallest and largest values in an array.
Initialize with the first element, then traverse from index 1.

1
public class Program
2
{
3
    public static void main(String[] args)
4
    {
5
        // Task 1 — Review: Min & Max
6
        int[] nums = {4, 7, 2, 9, 5};
7

8
        int min = nums[0];
9
        int max = nums[0];
10

11
        for (int i = 1; i < nums.length; i++)
12
        {
13
            if (nums[i] < min)
14
            {
15
                min = nums[i];
16
            }
17

18
            if (nums[i] > max)
19
            {
20
                max = nums[i];
21
            }
22
        }
23

24
        System.out.println("Min: " + min);
25
        System.out.println("Max: " + max);
26
    }
27
}

Task 2: Swap Algorithm

Swap two elements using a temporary variable.
Print the array using traversal (one element per line).
Optional: do a second swap and print again.

1
public class Program
2
{
3
    public static void main(String[] args)
4
    {
5
        // Task 2 — Swap Algorithm (precursor to sorting)
6
        int[] nums = {10, 20, 30, 40};
7

8
        // 1) Swap index 0 and index 3
9
        int temp = nums[0];
10
        nums[0] = nums[3];
11
        nums[3] = temp;
12

13
        // 2) Print each element on its own line (use traversal)
14
        for (int i = 0; i < nums.length; i++)
15
        {
16
            System.out.println(nums[i]);
17
        }
18

19
        // 3) Challenge (optional): swap index 1 and index 2, then print again.
20
    }
21
}

Task 3: Linear Search (AP Required)

Search for a target value.
Print both a boolean (found) and an index (foundIndex).
Use -1 as the “not found” index.

1
public class Program
2
{
3
    public static void main(String[] args)
4
    {
5
        // Task 3 — Linear Search (AP Required)
6
        int[] nums = {4, 7, 2, 9, 5};
7
        int target = 9;
8

9
        boolean found = false;
10
        int foundIndex = -1;
11

12
        for (int i = 0; i < nums.length; i++)
13
        {
14
            if (nums[i] == target)
15
            {
16
                found = true;
17
                foundIndex = i;
18
            }
19
        }
20

21
        System.out.println("Found: " + found);
22
        System.out.println("Index: " + foundIndex);
23
    }
24
}

Task 4: Binary Search (Optional Enrichment)

Only works on a sorted array.
Use low, high, and mid to cut the search space in half.
Print a boolean and index just like Task 3.

1
public class Program
2
{
3
    public static void main(String[] args)
4
    {
5
        // Task 4 — Binary Search (ENRICHMENT / FOR FUN)
6
        // Not required for the AP CSA exam
7
        int[] nums = {2, 4, 7, 9, 12, 15};
8
        int target = 12;
9

10
        int low = 0;
11
        int high = nums.length - 1;
12

13
        boolean found = false;
14
        int foundIndex = -1;
15

16
        while (low <= high)
17
        {
18
            int mid = (low + high) / 2;
19

20
            if (nums[mid] == target)
21
            {
22
                found = true;
23
                foundIndex = mid;
24
                break;
25
            }
26
            else if (nums[mid] < target)
27
            {
28
                low = mid + 1;
29
            }
30
            else
31
            {
32
                high = mid - 1;
33
            }
34
        }
35

36
        System.out.println("Found: " + found);
37
        System.out.println("Index: " + foundIndex);
38
    }
39
}

Sample Output

Your program output should something similar to the sample output below.

Min: 2
Max: 9
40
20
30
10
Found: true
Index: 3
Found: true
Index: 4

Reflection Questions

You may write your reflection answers as comments at the bottom of your code.

Why does swapping require a temporary variable?
What value do we use for foundIndex when the target is not found? Why is that useful?
How is binary search different from linear search (in words, not code)?
Why must the array be sorted for binary search?
Which searching algorithm is required for the AP CSA exam?

Submission

Submit your activity and reflection answers to the appropriate dropbox.