Unit 4 Overview

Unit 4: Data Collections is the largest and most important unit on the AP CSA Exam. It covers everything from basic arrays to complex algorithms, and accounts for nearly 40% of your exam score.

What's New for 2025-2026

Unit 4 Topic Breakdown

Arrays

An array is a container that holds a fixed number of values of a single type. Once created, an array's size cannot change. Arrays are the foundation of data collections in Java.

Creating Arrays

Method 1: Declare Size (Elements Get Default Values)

// Create array of 5 integers - all initialized to 0
int[] numbers = new int[5];
// numbers = [0, 0, 0, 0, 0]

// Create array of 3 Strings - all initialized to null
String[] names = new String[3];
// names = [null, null, null]

// Create array of 4 doubles - all initialized to 0.0
double[] prices = new double[4];

Method 2: Initialize with Values (Size Inferred)

int[] scores = {85, 90, 78, 92, 88};   // length = 5
String[] colors = {"red", "green", "blue"}; // length = 3

Default Values by Type

Accessing and Modifying Elements

int[] arr = {10, 20, 30, 40, 50};

// Access elements using index (0-based!)
System.out.println(arr[0]);              // 10  (first element)
System.out.println(arr[2]);              // 30  (third element)
System.out.println(arr[arr.length - 1]);  // 50  (last element)

// Get array length (no parentheses - it's a field, not a method)
System.out.println(arr.length);  // 5

// Modify elements
arr[0] = 100;              // [100, 20, 30, 40, 50]
arr[4] = arr[3] + 10;     // [100, 20, 30, 40, 50]

Array Index Diagram

//   Index:    0     1     2     3     4
//          +-----+-----+-----+-----+-----+
//   arr:   | 10  | 20  | 30  | 40  | 50  |
//          +-----+-----+-----+-----+-----+
//
//   arr.length = 5
//   Valid indices: 0 through arr.length - 1  (0 through 4)
//   First element: arr[0]
//   Last element:  arr[arr.length - 1]  =  arr[4]

int[] arr = {10, 20, 30};  // valid indices: 0, 1, 2
arr[3];          // CRASH! Index 3 doesn't exist
arr[-1];         // CRASH! Negative indices don't exist
arr[arr.length]; // CRASH! arr.length = 3, so arr[3] is out of bounds

Arrays of Objects

// Array of String objects - initialized to null, NOT empty strings!
String[] words = new String[3];
// words = [null, null, null]

words[0] = "Hello";
words[1] = "World";
// words = ["Hello", "World", null]

// Calling a method on null causes NullPointerException!
if (words[2] != null)               // Always null-check first
    System.out.println(words[2].length());  // Safe

int[] a = {1, 2, 3};
int[] b = a;  // b points to the SAME array as a (alias!)

b[0] = 99;
System.out.println(a[0]);  // 99 — a was also changed!

// To make an independent copy, loop and copy each element:
int[] copy = new int[a.length];
for (int i = 0; i < a.length; i++)
    copy[i] = a[i];

Array Traversals

Traversing an array means visiting each element to read, process, or modify its value. There are five traversal patterns you need to know for the AP exam.

Pattern 1: Standard for Loop

Use when you need the index, need to modify elements, or need to compare adjacent elements.

int[] arr = {10, 20, 30, 40, 50};

for (int i = 0; i < arr.length; i++)
    System.out.println("Index " + i + ": " + arr[i]);
// Index 0: 10  |  Index 1: 20  |  ...  |  Index 4: 50

for (int i = 0; i < arr.length; i++)   // ✔ Correct: 0 to length-1
for (int i = 0; i <= arr.length; i++)  // ✖ Crash: tries arr[length]

Pattern 2: Enhanced for Loop (for-each)

Use when you only need to read values and don't need the index. Cleaner syntax, but cannot modify.

for (int num : arr)
    System.out.println(num);
// Output: 10, 20, 30, 40, 50 (each on new line)

// Works with String arrays too:
String[] words = {"apple", "banana", "cherry"};
for (String word : words)
    System.out.println(word.toUpperCase());
// APPLE  BANANA  CHERRY

int[] arr = {10, 20, 30};
for (int num : arr)
    num = num * 2;  // Only changes local copy — array UNCHANGED
// arr is still [10, 20, 30]

// To modify, use a standard for loop:
for (int i = 0; i < arr.length; i++)
    arr[i] = arr[i] * 2;  // This DOES modify: [20, 40, 60]

Pattern 3: Backward Traversal

Essential for removing elements from ArrayList while traversing.

for (int i = arr.length - 1; i >= 0; i--)
    System.out.println(arr[i]);
// Output: 50, 40, 30, 20, 10

Pattern 4: Partial Traversal

int[] arr = {10, 20, 30, 40, 50, 60};

// First half only
for (int i = 0; i < arr.length / 2; i++)
    System.out.print(arr[i] + " ");  // 10 20 30

// Every other element (even indices)
for (int i = 0; i < arr.length; i += 2)
    System.out.print(arr[i] + " ");  // 10 30 50

// Every other element (odd indices)
for (int i = 1; i < arr.length; i += 2)
    System.out.print(arr[i] + " ");  // 20 40 60

Pattern 5: Accessing Adjacent Elements

Used to compare neighbors — requires careful bounds to avoid crashing.

int[] arr = {10, 20, 30, 40, 50};

// Compare each element with the NEXT one (stop at length - 1!)
for (int i = 0; i < arr.length - 1; i++)
{
    if (arr[i] > arr[i + 1])
        System.out.println(arr[i] + " > " + arr[i + 1]);
}

// Compare each element with the PREVIOUS one (start at 1!)
for (int i = 1; i < arr.length; i++)
{
    if (arr[i] < arr[i - 1])
        System.out.println(arr[i] + " < " + arr[i - 1]);
}

Array Algorithms

These are the standard algorithms the AP exam tests most heavily. Memorize every pattern — they appear in both MCQ tracing and FRQ writing.

Algorithm 1: Sum of Elements

int[] arr = {10, 20, 30, 40, 50};
int sum = 0;  // accumulator starts at 0
for (int num : arr)
    sum += num;
System.out.println(sum);  // 150

Algorithm 2: Average of Elements

int sum = 0;
for (int num : arr) sum += num;

// MUST cast to double before dividing - otherwise integer division!
double average = (double) sum / arr.length;
// Without cast: 150 / 5 = 30  (truncates)
// With cast:    150.0 / 5 = 30.0  (correct)

Algorithm 3: Find Maximum

int[] arr = {23, 45, 12, 67, 34};

// Initialize to FIRST element, never to 0
int max = arr[0];
for (int i = 1; i < arr.length; i++)  // start at 1
    if (arr[i] > max) max = arr[i];
System.out.println(max);  // 67

int[] arr = {-5, -3, -8, -1};
int max = 0;     // WRONG: 0 isn't even in the array!
int max = arr[0]; // ✔ Correct: -5, updates to -1

Algorithm 4: Find Minimum

int min = arr[0];
for (int i = 1; i < arr.length; i++)
    if (arr[i] < min) min = arr[i];  // just flip > to <

Algorithm 5: Count Occurrences

int[] arr = {5, 3, 5, 7, 5, 2};
int target = 5;
int count = 0;
for (int num : arr)
    if (num == target) count++;
System.out.println(count);  // 3

Algorithm 6: Count Elements Meeting a Condition

int[] arr = {12, 7, 25, 3, 18, 9};

int evenCount = 0;
for (int num : arr)
    if (num % 2 == 0) evenCount++;  // 2 (12 and 18)

int bigCount = 0;
for (int num : arr)
    if (num > 10) bigCount++;  // 3 (12, 25, 18)

Algorithm 7: Check if ANY Element Meets a Condition

// Start false, flip to true if you find one match
boolean hasNegative = false;
for (int num : arr)
    if (num < 0) hasNegative = true;

Algorithm 8: Check if ALL Elements Meet a Condition

// Start true, flip to false if any element fails
boolean allPositive = true;
for (int num : arr)
    if (num <= 0) allPositive = false;

Algorithm 9: Shift Elements Left

int[] arr = {1, 2, 3, 4, 5};
// Traverse FORWARD: each element gets the value of the next one
for (int i = 0; i < arr.length - 1; i++)
    arr[i] = arr[i + 1];
arr[arr.length - 1] = 0;  // clear last position
// arr = [2, 3, 4, 5, 0]

Algorithm 10: Shift Elements Right

int[] arr = {1, 2, 3, 4, 5};
// Traverse BACKWARD: each element gets the value of the previous one
for (int i = arr.length - 1; i > 0; i--)
    arr[i] = arr[i - 1];
arr[0] = 0;  // clear first position
// arr = [0, 1, 2, 3, 4]

Algorithm 11: Reverse an Array

int[] arr = {1, 2, 3, 4, 5};
// Swap elements from outside in, only go halfway
for (int i = 0; i < arr.length / 2; i++)
{
    int temp = arr[i];
    arr[i] = arr[arr.length - 1 - i];
    arr[arr.length - 1 - i] = temp;
}
// Trace: swap arr[0]&arr[4] → [5,2,3,4,1]
//        swap arr[1]&arr[3] → [5,4,3,2,1]
//        i=2 is NOT < 5/2=2, loop ends
// arr = [5, 4, 3, 2, 1]

Algorithm 12: Copy an Array

int[] original = {1, 2, 3, 4, 5};
int[] copy = new int[original.length];
for (int i = 0; i < original.length; i++)
    copy[i] = original[i];

copy[0] = 99;
// copy = [99, 2, 3, 4, 5]
// original = [1, 2, 3, 4, 5] (unchanged)

Using Text Files NEW for 2025-2026

The College Board added file I/O to the curriculum. Use the File and Scanner classes to read data from text files.

Basic File Reading Pattern

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public static void readData() throws IOException
{
    File myFile = new File("data.txt");
    Scanner input = new Scanner(myFile);
    while (input.hasNext())
    {
        String line = input.nextLine();
        System.out.println(line);
    }
    input.close();
}

Scanner Methods for Files

Reading Numbers into an ArrayList

public static ArrayList<Integer> loadNumbers(String filename) throws IOException
{
    ArrayList<Integer> numbers = new ArrayList<Integer>();
    Scanner input = new Scanner(new File(filename));
    while (input.hasNext())
        numbers.add(input.nextInt());  // autoboxing: int → Integer
    input.close();
    return numbers;
}

Wrapper Classes

ArrayLists can only hold objects, not primitive types. Wrapper classes wrap each primitive in an object so it can be stored in an ArrayList.

Primitive Types and Their Wrappers

Autoboxing: Automatic Primitive → Object

// Java automatically converts primitives to wrapper objects
Integer num = 42;    // int 42 is "boxed" into an Integer object
Double price = 9.99; // double is boxed into Double

// Autoboxing happens automatically when adding to ArrayList
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(10);  // int 10 autoboxed to Integer
numbers.add(20);
numbers.add(30);

Unboxing: Automatic Object → Primitive

Integer numObj = 42;
int numPrim = numObj;  // Integer is automatically "unboxed" to int

// Unboxing happens automatically when getting from ArrayList
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(100);
int value = numbers.get(0);       // Integer unboxed to int
int doubled = numbers.get(0) * 2; // unboxing happens automatically

Integer num = null;
int x = num + 5;  // CRASH! Can't unbox null

// Can also happen with ArrayList:
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(null);          // legal - ArrayList can store null
int val = list.get(0);  // CRASH! Unboxing null

Useful Integer Methods

// Convert String to int
int num = Integer.parseInt("123");  // 123

// Maximum and minimum int values
int maxInt = Integer.MAX_VALUE;  // 2147483647
int minInt = Integer.MIN_VALUE;  // -2147483648

// Convert String to double
double pi = Double.parseDouble("3.14159");  // 3.14159

ArrayList

An ArrayList is a resizable array. Unlike a fixed array, you can add and remove elements at any time. It is the most-tested data structure on FRQ #3.

Creating an ArrayList

import java.util.ArrayList;

// Declare and initialize (empty)
ArrayList<String> names = new ArrayList<String>();
ArrayList<Integer> nums = new ArrayList<Integer>();

All ArrayList Methods

Complete Traced Example

ArrayList<String> list = new ArrayList<String>();
list.add("A");       // [A]              size=1
list.add("B");       // [A, B]           size=2
list.add("C");       // [A, B, C]        size=3
list.add(1, "X");   // [A, X, B, C]     size=4  (B, C shift right)
list.set(0, "Z");    // [Z, X, B, C]     size=4  (A replaced)
list.remove(2);      // [Z, X, C]        size=3  (B removed, C shifts left)
System.out.println(list.get(1));  // X
System.out.println(list.size());   // 3

Traversing an ArrayList

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(10); nums.add(20); nums.add(30);

// Standard for loop (use when you need the index)
for (int i = 0; i < nums.size(); i++)
    System.out.println(nums.get(i));

// Enhanced for loop (cleaner, use when you only need values)
for (int num : nums)
    System.out.println(num);

ArrayList<String> list = new ArrayList<String>();
list.add("hello");

// WRONG: == compares references, not content
if (list.get(0) == "hello") ...    // may be false!

// CORRECT: .equals() compares string content
if (list.get(0).equals("hello")) ...  // ✔ always correct

ArrayList Algorithms

ArrayList algorithms are heavily tested on FRQ #3. The most important distinction from array algorithms is how you handle removal — getting this wrong is the most common FRQ mistake.

ArrayList<Integer> list = new ... // [1, 2, 3, 4]

// WRONG — when element is removed, next element shifts left
// and gets skipped by i++ :
for (int i = 0; i < list.size(); i++)
    if (list.get(i) % 2 == 0) list.remove(i);
// Result: [1, 3]  -- wrong! Should be [1, 3] but arrives there wrong
// Worse: if two consecutive evens [2, 4], the 4 gets skipped entirely

// CORRECT — traverse backward so shifts don't affect unvisited indices
for (int i = list.size() - 1; i >= 0; i--)
    if (list.get(i) % 2 == 0) list.remove(i);

Algorithm 1: Remove All Occurrences of a Value

public static void removeAll(ArrayList<String> list, String target)
{
    for (int i = list.size() - 1; i >= 0; i--)
        if (list.get(i).equals(target))
            list.remove(i);
}

Algorithm 2: Filter into a New List

When you want to keep elements that meet a condition, build a new list rather than removing from the original.

public static ArrayList<Integer> getEvens(ArrayList<Integer> nums)
{
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int n : nums)
        if (n % 2 == 0) result.add(n);
    return result;
}

Algorithm 3: Find Maximum in an ArrayList

public static int findMax(ArrayList<Integer> nums)
{
    int max = nums.get(0);  // initialize to first element
    for (int n : nums)
        if (n > max) max = n;
    return max;
}

Algorithm 4: Count Elements Meeting a Condition

public static int countAbove(ArrayList<Integer> nums, int threshold)
{
    int count = 0;
    for (int n : nums)
        if (n > threshold) count++;
    return count;
}

Algorithm 5: Sum of All Elements

public static int sumList(ArrayList<Integer> nums)
{
    int sum = 0;
    for (int n : nums) sum += n;
    return sum;
}

Algorithm 6: Find and Update In-Place

// Double every element greater than 10
for (int i = 0; i < list.size(); i++)
    if (list.get(i) > 10)
        list.set(i, list.get(i) * 2);

2D Arrays

A 2D array is an array of arrays — think of it as a grid or table with rows and columns. FRQ #4 is always a 2D array problem.

Creating 2D Arrays

// Method 1: Declare size (all elements get default value 0)
int[][] grid = new int[3][4];  // 3 rows, 4 columns

// Method 2: Initialize with values
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
// 3 rows, 3 columns

Accessing Elements and Dimensions

// Access: [row][col] — row first, ALWAYS
System.out.println(matrix[0][0]);  // 1  (row 0, col 0)
System.out.println(matrix[1][2]);  // 6  (row 1, col 2)
System.out.println(matrix[2][1]);  // 8  (row 2, col 1)

// Get dimensions
System.out.println(matrix.length);       // 3 (number of rows)
System.out.println(matrix[0].length);  // 3 (number of columns)

// Modify elements
matrix[1][1] = 99;  // row 1, col 1 changed to 99

2D Array Diagram

//          col 0  col 1  col 2
// row 0:  [  1  ] [  2  ] [  3  ]    matrix[0][0]=1  matrix[0][2]=3
// row 1:  [  4  ] [  5  ] [  6  ]    matrix[1][1]=5  matrix[1][2]=6
// row 2:  [  7  ] [  8  ] [  9  ]    matrix[2][0]=7  matrix[2][2]=9

matrix[1][2]       // Row 1, Col 2 → 6  ✔
matrix[2][1]       // Row 2, Col 1 → 8  (different element!)
matrix.length      // Number of ROWS = 3
matrix[0].length   // Number of COLUMNS = 3

Row-Major Traversal (most common)

Outer loop = rows, inner loop = columns. Visits elements left to right, row by row.

for (int r = 0; r < matrix.length; r++)
{
    for (int c = 0; c < matrix[0].length; c++)
    {
        System.out.print(matrix[r][c] + " ");
    }
    System.out.println();  // newline after each row
}
// Output:
// 1 2 3
// 4 5 6
// 7 8 9

Column-Major Traversal

Outer loop = columns, inner loop = rows. Visits elements top to bottom, column by column.

for (int c = 0; c < matrix[0].length; c++)
{
    for (int r = 0; r < matrix.length; r++)
        System.out.print(matrix[r][c] + " ");
}
// Output: 1 4 7  2 5 8  3 6 9

Enhanced for Loop with 2D Arrays

// "for each row, for each element in that row"
for (int[] row : matrix)
    for (int val : row)
        System.out.print(val + " ");

2D Array Algorithms

2D array algorithms always use nested loops — outer for rows, inner for columns (row-major). FRQ #4 is always a 2D array problem.

Algorithm 1: Sum All Elements

public static int sumAll(int[][] arr)
{
    int sum = 0;
    for (int r = 0; r < arr.length; r++)
        for (int c = 0; c < arr[0].length; c++)
            sum += arr[r][c];
    return sum;
}

Algorithm 2: Count Elements Meeting a Condition

public static int countPositive(int[][] arr)
{
    int count = 0;
    for (int r = 0; r < arr.length; r++)
        for (int c = 0; c < arr[0].length; c++)
            if (arr[r][c] > 0) count++;
    return count;
}

Algorithm 3: Sum a Single Row

public static int rowSum(int[][] arr, int row)
{
    int sum = 0;
    for (int c = 0; c < arr[0].length; c++)
        sum += arr[row][c];
    return sum;
}

Algorithm 4: Sum a Single Column

public static int colSum(int[][] arr, int col)
{
    int sum = 0;
    for (int r = 0; r < arr.length; r++)
        sum += arr[r][col];
    return sum;
}

Algorithm 5: Find Maximum in a 2D Array

public static int findMax(int[][] arr)
{
    int max = arr[0][0];  // initialize to first element
    for (int r = 0; r < arr.length; r++)
        for (int c = 0; c < arr[0].length; c++)
            if (arr[r][c] > max) max = arr[r][c];
    return max;
}

Algorithm 6: Check if Any Row Contains a Value

public static boolean rowContains(int[][] arr, int row, int val)
{
    for (int c = 0; c < arr[0].length; c++)
        if (arr[row][c] == val) return true;
    return false;
}

Algorithm 7: Copy All Elements to a New 2D Array

public static int[][] copy2D(int[][] arr)
{
    int[][] result = new int[arr.length][arr[0].length];
    for (int r = 0; r < arr.length; r++)
        for (int c = 0; c < arr[0].length; c++)
            result[r][c] = arr[r][c];
    return result;
}

4.14 — Searching Algorithms

The AP exam tests two searching algorithms exclusively: linear search and binary search. You must be able to trace both, identify which is appropriate for a given scenario, and spot errors in their implementations.

Linear Search

Linear search checks every element one at a time from left to right. It works on any array — sorted or unsorted.

// Returns index of target, or -1 if not found
public static int linearSearch(int[] arr, int target) {
    for (int k = 0; k < arr.length; k++) {
        if (arr[k] == target) {
            return k;       // return index, not the value
        }
    }
    return -1;            // -1 signals "not found"
}

Step-by-Step Trace

Array: {14, 7, 31, 9, 22} Target: 9

Binary Search

Binary search repeatedly cuts the search range in half. It is dramatically faster than linear search — but it requires a sorted array.

// Iterative binary search — returns index of target, or -1
// PRECONDITION: arr is sorted in ascending order
public static int binarySearch(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            lo = mid + 1;   // target is in right half
        } else {
            hi = mid - 1;   // target is in left half
        }
    }
    return -1;
}

Step-by-Step Trace

Sorted array: {3, 8, 12, 19, 25, 34, 47} Target: 19 Indices: 0–6

Now trace a miss. Target: 20

public static int locate(int[] arr, int target) {
    for (int k = 0; k <= arr.length; k++) {   // Line 2
        if (arr[k] == target) {
            return k;
        }
    }
    return -1;
}

public static int bFind(int[] arr, int val, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = (lo + hi) / 2;
    if (arr[mid] == val) return mid;
    if (arr[mid] < val)
        return bFind(arr, val, lo, mid - 1);  // Line 6
    return bFind(arr, val, mid + 1, hi);
}

4.15 — Sorting Algorithms

The AP exam tests selection sort and insertion sort exclusively. You must trace them pass by pass. You will never be asked to write them from scratch on the MCQ — but you must read them fluently and predict what the array looks like after k passes.

Selection Sort

On each pass, selection sort finds the minimum in the unsorted portion and swaps it into position. After k passes, the first k elements are in their final sorted positions.

public static void selectionSort(int[] data) {
    for (int j = 0; j < data.length - 1; j++) {
        int minIdx = j;
        for (int k = j + 1; k < data.length; k++) {
            if (data[k] < data[minIdx]) {
                minIdx = k;
            }
        }
        int temp = data[j];
        data[j] = data[minIdx];
        data[minIdx] = temp;
    }
}

Pass-by-Pass Trace

Starting array: {42, 17, 35, 8, 26}

Insertion Sort

Insertion sort builds a sorted sub-array on the left. On each pass, it picks the next element and inserts it into the correct position by shifting larger elements rightward.

public static void insertionSort(int[] data) {
    for (int j = 1; j < data.length; j++) {
        int temp = data[j];
        int pos = j - 1;
        while (pos >= 0 && data[pos] > temp) {
            data[pos + 1] = data[pos];
            pos--;
        }
        data[pos + 1] = temp;
    }
}

Pass-by-Pass Trace

Starting array: {42, 17, 35, 8, 26}

Key Differences: Selection vs. Insertion

public static void sSort(int[] d) {
    for (int j = 0; j < d.length - 1; j++) {
        int m = j;
        for (int k = j + 1; k < d.length; k++) {
            if (d[k] < d[m]) m = k;
        }
        int t = d[j]; d[j] = d[m]; d[m] = t;
    }
}

public static void iSort(int[] d) {
    for (int j = 1; j < d.length; j++) {
        int tmp = d[j];
        int p = j - 1;
        while (p >= 0 && d[p] > tmp) {
            d[p + 1] = d[p];
            p--;
        }
        d[p] = tmp;   // Line 8
    }
}

4.16 / 4.17 — Recursion & Recursive Searching/Sorting

Anatomy of a Recursive Method

Every correct recursive method has exactly two components:

// Classic example: sum of digits
public static int digitSum(int n) {
    if (n < 10)               // BASE CASE: single digit
        return n;
    return (n % 10) + digitSum(n / 10);  // RECURSIVE CASE
}

How to Trace a Recursive Method

Use the call stack model. Each call is pushed onto the stack. Once the base case is reached, calls start returning and the stack unwinds.

Trace: digitSum(347)

Phase 1 — Building the call stack:

Phase 2 — Unwinding:

Common Recursive Patterns on the AP Exam

Recursive Binary Search (4.17)

/** Precondition: arr is sorted ascending.
 *  Returns index of val, or -1 if not found. */
public static int rBinSearch(int[] arr, int val, int lo, int hi) {
    if (lo > hi)            // BASE CASE: range exhausted
        return -1;
    int mid = (lo + hi) / 2;
    if (arr[mid] == val)    // BASE CASE: found it
        return mid;
    if (arr[mid] < val)
        return rBinSearch(arr, val, mid + 1, hi);  // search right
    return rBinSearch(arr, val, lo, mid - 1);      // search left
}

This is identical in logic to iterative binary search — the only difference is that the loop is replaced with recursive calls. The call stack builds up to O(log n) levels deep.

public static int proc(int n) {
    if (n <= 0) return 5;
    return n + proc(n - 2);
}

public static void printIt(String s) {
    if (s.length() == 0) return;
    System.out.print(s.substring(s.length() - 1));
    printIt(s.substring(0, s.length() - 1));
}

Common Exam Traps

1. Off-by-One Loop Bounds

2. length vs length() vs size()

3. 2D Array [row][col]

4. String Comparison

5. Enhanced for Can't Modify

for (int num : arr)
    num = num * 2;  // Only changes local copy — array unchanged!

6. Initialize max to arr[0], not 0

int max = 0;       // Fails for all-negative arrays
int max = arr[0];  // ✔ Correct

7. Binary Search Needs Sorted Data

int[] unsorted = {50, 10, 30};
binarySearch(unsorted, 30);  // Unpredictable result!

Practice Questions

int[] arr = {2, 4, 6, 8, 10};
int sum = 0;
for (int i = 0; i < arr.length; i += 2)
    sum += arr[i];
System.out.println(sum);

int[] arr = {1, 2, 3};
for (int num : arr)
    num = num + 10;
System.out.println(arr[1]);

int[][] grid = {{1,2,3}, {4,5,6}, {7,8,9}};
System.out.println(grid[2][0] + grid[0][2]);

ArrayList<String> list = new ArrayList<String>();
list.add("A"); list.add("B"); list.add("C");
list.add(1, "X");
list.remove(2);
System.out.println(list);

FRQ Practice

public static int countAbove(ArrayList<Integer> scores, int threshold)

public static void removeBelow(ArrayList<Integer> scores, int passing)

public static int countAbove(ArrayList<Integer> scores, int threshold)
{
    int count = 0;
    for (int score : scores)
        if (score > threshold) count++;
    return count;
}

public static void removeBelow(ArrayList<Integer> scores, int passing)
{
    for (int i = scores.size() - 1; i >= 0; i--)
        if (scores.get(i) < passing)
            scores.remove(i);
}

public static int countEmpty(String[][] chart)

public static int countEmpty(String[][] chart)
{
    int count = 0;
    for (int r = 0; r < chart.length; r++)
        for (int c = 0; c < chart[0].length; c++)
            if (chart[r][c] == null) count++;
    return count;
}

public static ArrayList<Integer> loadData(String filename) throws IOException

public static ArrayList<Integer> loadData(String filename) throws IOException
{
    ArrayList<Integer> data = new ArrayList<Integer>();
    Scanner input = new Scanner(new File(filename));
    while (input.hasNext())
        data.add(input.nextInt());
    input.close();
    return data;
}

Quick Reference

Algorithm Complexity

Final Checklist

• < not <= for loop bounds
• .length / .length() / .size()
• grid[row][col] not grid[col][row]
• Remove from ArrayList BACKWARD
• .equals() for Strings, not ==
• Binary search requires a SORTED array
• Initialize max/min to arr[0], not 0
• Enhanced for loop cannot modify array elements
• throws IOException required for file reading