Historical Context & Motivation
Every program of practical significance must make decisions and repeat actions. Before electronic computers existed, mathematicians formalized the notion of an algorithm — a finite sequence of well-defined steps that transforms inputs into outputs. The two indispensable building blocks identified in that formalization were selection (choosing among alternatives) and repetition (executing steps multiple times). Without these constructs, programs could only perform a fixed, linear series of instructions, making them essentially useless for real-world problems.
The central question this lesson addresses is: how do we combine selection and iteration in Java to write algorithms that solve non-trivial problems — searching for values, accumulating results, filtering data, and processing strings? Understanding these patterns is essential because the AP Computer Science A exam tests your ability to trace, write, and analyze code that weaves together conditionals and loops.
Core Principles & Definitions
Selection and iteration are the two non-sequential control structures in Java. Selection lets a program branch its execution path based on a Boolean condition, while iteration lets a program repeat a block of code until a condition changes. When combined, they enable algorithms of arbitrary complexity. The following foundational concepts underpin every algorithm you will encounter on the AP exam.
Selection (if / else if / else)
if, else if, and else keywords implement single-selection, double-selection, and multi-way selection.Iteration (for / while)
for loop is ideal when the number of iterations is known; a while loop is preferred when termination depends on a runtime condition.Boolean Expressions
&& (AND), || (OR), and ! (NOT) with short-circuit evaluation.Algorithmic Patterns
Tracing & Correctness
Visual Explanation — Control Flow
i < n) is the loop condition. Each iteration enters the inner diamond (arr[i] > max), which is a selection inside the loop — the classic find-maximum pattern.The diagram illustrates the most common algorithmic pattern on the AP exam: a selection nested inside iteration. The outer loop iterates through array indices, and on each pass the inner conditional determines whether the current element should update the tracked maximum. Notice that the false branch of the inner diamond simply skips the update and proceeds to i++. This structure generalizes: replace the inner condition with any predicate and replace the update with any action, and you have searching, counting, filtering, or accumulating.
How Selection & Iteration Work in Java
Selection Constructs
Java provides three selection patterns. A single if statement executes its body only when the condition is true. An if-else guarantees exactly one of two blocks runs. A chained if / else if / else sequence tests conditions top-to-bottom and executes the first matching branch; subsequent conditions are skipped entirely. A subtle but exam-critical point is that Java uses short-circuit evaluation: in A && B, B is never evaluated if A is false, and in A || B, B is never evaluated if A is true.
Iteration Constructs
The for loop bundles initialization, condition, and update into one line: for (init; condition; update). The condition is checked before each iteration, so the body may execute zero times. The while loop expresses the same logic but separates the three components, making it the better choice when the number of iterations cannot be predetermined. Java's enhanced for-each loop (for (Type x : collection)) simplifies traversal but does not expose the index. All three loop forms appear on the AP exam.
Nesting Selection Inside Iteration
Algorithms become powerful when an if statement sits inside a loop body. On each iteration, the conditional selects whether to perform an action on the current element. This composite structure is the backbone of four fundamental patterns the AP exam tests: accumulate (sum or count matching elements), search (find an element satisfying a condition), min/max (track the extreme value), and filter/transform (build a new result based on a predicate).
Algorithmic Pattern Catalog
The AP Computer Science A exam repeatedly tests a small set of canonical algorithmic patterns. Each pattern combines iteration with selection in a specific way. Recognizing these patterns quickly is the key to both MCQ speed and FRQ accuracy. The diagram below categorizes the four main patterns and shows the essential code skeleton for each.
A few important notes apply across all four patterns. First, every pattern has O(n) time complexity because each element is visited exactly once. Second, the min/max pattern must initialize the tracking variable to an actual element (typically arr[0]), not to zero or Integer.MAX_VALUE — the AP exam frequently exploits this misunderstanding. Third, for the search pattern, returning inside the loop provides an early exit, which is more efficient than searching the entire array when a match exists.
Worked Example — Counting Even Digits
Consider the following method that counts how many even digits appear in a non-negative integer. This example demonstrates a while loop (since the number of digits is not known at compile time) with an if selection inside.
n = 3842 and count = 0. The while condition 3842 > 0 is true, so we enter the loop.digit = 3842 % 10 = 2. Since 2 % 2 == 0 is true, count increments to 1. Then n = 3842 / 10 = 384.digit = 384 % 10 = 4. Since 4 % 2 == 0 is true, count increments to 2. Then n = 384 / 10 = 38.digit = 38 % 10 = 8. Since 8 % 2 == 0 is true, count increments to 3. Then n = 38 / 10 = 3.digit = 3 % 10 = 3. Since 3 % 2 == 0 is false, count stays at 3. Then n = 3 / 10 = 0.0 > 0 is false, so the loop exits. The method returns 3. Indeed, the integer 3842 contains three even digits (2, 4, 8).Comparing Loop Constructs
Java offers three loop constructs that are appropriate for the AP subset. Each has strengths and constraints, and choosing the right one can make your code both cleaner and less error-prone. The table below summarizes when to prefer each form.
| Feature | for loop | while loop | for-each loop |
|---|---|---|---|
| Best when | Number of iterations is known or index-driven | Termination depends on a dynamic condition | Every element must be visited; no index needed |
| Access to index? | Yes | Yes (if you manage it) | No |
| Off-by-one risk | Moderate — < vs. <= | Higher — manual updates | None — automatic |
| Can modify collection? | Yes (with index) | Yes (with index) | No — ConcurrentModificationException |
| AP exam frequency | Very high | High | Moderate |
Connection to Advanced Topics
The selection-inside-iteration pattern studied in this lesson is the foundation on which more advanced algorithms are built. Once you are comfortable nesting a single conditional inside a single loop, you are ready for nested loops (iteration within iteration) and recursive decomposition (where the loop is replaced by a method calling itself). The table below maps the patterns from this lesson to their more advanced counterparts.
| This Lesson | Advanced Extension | Where Tested |
|---|---|---|
| Linear search (single loop) | Binary search (selection with halving) | AP CSA Unit 7 / FRQ |
| Find max (single loop + if) | Selection sort (nested loop + swap) | AP CSA Unit 7 |
| Accumulate pattern | Merge sort merge step | AP CSA Unit 7 |
| String traversal with charAt() | Recursive string processing | AP CSA Unit 10 / FRQ |
| Filter (single array) | 2D array traversal (nested for loops) | AP CSA Unit 8 / FRQ |
A critical skill as you advance is recognizing that nested loops change the time complexity from O(n) to O(n²). Binary search, in contrast, achieves O(log n) by leveraging selection to halve the search space on every iteration — a dramatic improvement that stems from the same if-else construct you already know. The transition from Unit 4 (this lesson's material) to Units 7–10 is essentially the transition from flat composition (one loop, one if) to deep composition (nested loops, recursive calls), all using the same building blocks.
Practice Problems
int x = 5;
while (x > 0) {
if (x % 2 == 1)
System.out.print(x + " ");
x--;
}
What is printed as a result of executing this code?
A. 5 3 1
B. 5 4 3 2 1
C. 4 2
D. 1 3 5int[] arr = {3, 7, 2, 8, 5};
int sum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 4)
sum += arr[i];
}
System.out.println(sum);
What is printed?
A. 25
B. 20
C. 15
D. 5String s = "aAbBcC";
String result = "";
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
result += s.charAt(i);
else
result += "*";
}
System.out.println(result);
What is printed?
A. a*b*c*
B. abc
C. *A*B*C
D. a*B*c*public static int longestRun(int[] arr) that returns the length of the longest consecutive run of equal values in arr. For example, if arr = {1, 1, 2, 2, 2, 3, 3}, the method returns 3 (the run of 2s). You may assume arr.length >= 1.public static boolean isPalindrome(String s) that returns true if s reads the same forwards and backwards (case-sensitive). Your solution must use a loop with selection. Explain why your loop only needs to iterate through half the string.