AP CS A — Searching & Sorting

01

What the AP Exam Covers

Searching Algorithms Unit 7

The AP exam tests two searching algorithms applied to arrays and ArrayLists:

Sequential (Linear) Search — works on any array, sorted or unsorted
Binary Search — requires a sorted array; much faster for large datasets

Sorting Algorithms Unit 7

Three sorting algorithms are explicitly required:

Selection Sort — simple, always O(n²)
Insertion Sort — great for nearly-sorted data
Merge Sort — efficient, divide-and-conquer, O(n log n)

Tip: You need to trace through these by hand on the exam — not just recognize names. Practice step-by-step execution.

02

Sequential Search

How It Works O(n)

Check each element one by one from left to right until you find the target or exhaust the array. No sorting required.

Best Case

O(1) — target is first element

Worst Case

O(n) — target is last or not found

Average Case

O(n) — check ~n/2 elements

Requires Sorted?

No — works on any array

// Sequential search — returns index or -1 if not found
public static int sequentialSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;   // found! return index
        }
    }
    return -1;       // not found
}
      

Watch out: If the array has duplicates, sequential search returns the first occurrence's index.

▶ Interactive: Sequential Search

Step through a sequential search for value 7 in the array below.

Press "Next Step" to begin searching for 7.

03

Binary Search

How It Works O(log n)

Repeatedly halve the search space. Compare the target to the middle element. If target is smaller, search the left half; if larger, search the right half. Repeat until found or bounds cross.

CRITICAL: The array must be sorted before binary search can be used. This is an exam favorite.

Best Case

O(1) — target is middle element

Worst Case

O(log n) — target not found

Requires Sorted?

YES — mandatory

Max comparisons (n=1000)

~10 comparisons (log₂1000 ≈ 10)

// Binary search — returns index or -1 if not found
public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;   // integer division

        if (arr[mid] == target) {
            return mid;              // found!
        } else if (arr[mid] < target) {
            low = mid + 1;           // search right half
        } else {
            high = mid - 1;          // search left half
        }
    }
    return -1;                       // not found
}
      

Key variables to track on the exam: low, high, mid. Examiners will ask you to trace these values.

▶ Interactive: Binary Search

Searching for 23 in a sorted array. Watch how low/mid/high move.

Press "Next Step" to begin binary search for 23.

        ■ mid
        ■ search range
        ■ found
        ■ eliminated
      

04

Selection Sort

How It Works O(n²)

Find the minimum element in the unsorted portion, swap it with the first unsorted element. Repeat, extending the sorted portion by one each pass.

Mental model: "Find the smallest, put it in place. Find the next smallest, put it in place. Repeat."

Best Case

O(n²) — always same behavior

Worst Case

O(n²)

Swaps per pass

At most 1 swap per pass

Stable?

No (can disrupt equal elements)

// Selection Sort — sorts array in ascending order
public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;   // assume current position is minimum

        // find the actual minimum in unsorted portion
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // swap minimum into position i
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}
      

Exam trap: Selection sort always makes exactly n−1 passes and n(n−1)/2 comparisons regardless of input order. It never "early exits."

Trace example — array: [5, 2, 8, 1, 9]

Pass 1: min=1 (idx 3) → swap idx 0 & 3 → [1, 2, 8, 5, 9]
Pass 2: min=2 (idx 1) → swap idx 1 & 1 → [1, 2, 8, 5, 9]
Pass 3: min=5 (idx 3) → swap idx 2 & 3 → [1, 2, 5, 8, 9]
Pass 4: min=8 (idx 3) → swap idx 3 & 3 → [1, 2, 5, 8, 9]
Done! ✓
      

05

Insertion Sort

How It Works O(n²) worst O(n) best

Take each element and insert it into its correct position within the already-sorted left portion. Shift elements right to make room.

Mental model: Like sorting playing cards in your hand — pick up each card and slide it left to its correct spot.

Best Case

O(n) — already sorted

Worst Case

O(n²) — reverse sorted

Nearly sorted?

Very fast — best practical use

Stable?

Yes

// Insertion Sort — sorts array in ascending order
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];   // element to insert
        int j = i - 1;

        // shift elements right while they're larger than key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;   // insert key into correct position
    }
}
      

Key insight: After each outer loop pass, the elements from index 0 to i are sorted — but they may not be in their final positions yet.

Trace example — array: [5, 2, 8, 1, 9]

i=1: key=2  → shift 5 right → [2, 5, 8, 1, 9]
i=2: key=8  → 8 > 5, no shift → [2, 5, 8, 1, 9]
i=3: key=1  → shift 8,5,2 right → [1, 2, 5, 8, 9]
i=4: key=9  → no shift → [1, 2, 5, 8, 9]
Done! ✓
      

06

Merge Sort

How It Works O(n log n)

A divide and conquer algorithm. Split the array in half, recursively sort each half, then merge the two sorted halves back together.

Mental model: Split until you have single elements (trivially sorted). Then merge pairs, then merge quadruples, etc.

Best Case

O(n log n)

Worst Case

O(n log n) — always!

Space

O(n) — needs extra array

Stable?

Yes

// Merge Sort — divide and conquer
public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);       // sort left half
        mergeSort(arr, mid + 1, right);  // sort right half
        merge(arr, left, mid, right);    // merge sorted halves
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])  temp[k++] = arr[i++];
        else                   temp[k++] = arr[j++];
    }
    while (i <= mid)   temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int m = 0; m < temp.length; m++)
        arr[left + m] = temp[m];
}
      

Divide phase — visualize this for [5, 2, 8, 1]:

// Splitting:
[5, 2, 8, 1]
 ↙          ↘
[5, 2]     [8, 1]
 ↙   ↘      ↙   ↘
[5]  [2]  [8]  [1]

// Merging back (comparing & sorting):
[5]  [2]  →  [2, 5]
[8]  [1]  →  [1, 8]
[2, 5] + [1, 8]  →  [1, 2, 5, 8] ✓
      

Why O(n log n)? There are log₂(n) levels of splitting. At each level, merging all elements takes O(n) total work. So total = O(n) × O(log n) = O(n log n).

07

Complexity Summary

Big-O Reference Table

Algorithm

Best

Worst

Sorted Required?

Sequential Search

O(1)

O(n)

No

Binary Search

O(1)

O(log n)

YES

Selection Sort

O(n²)

No

Insertion Sort

O(n)

O(n²)

No

Merge Sort

O(n log n)

No

Growth rate ranking (fastest → slowest): O(1) < O(log n) < O(n) < O(n log n) < O(n²)

Algorithm Comparison

Factor	Selection Sort	Insertion Sort	Merge Sort
Simplicity	Simple	Simple	Complex
Best for	Small arrays	Nearly sorted	Large arrays
Extra memory	O(1)	O(1)	O(n)
Swaps	At most n−1	Many shifts	No in-place
Uses recursion?	No	No	Yes

08

Exam Tips & Common Traps

🎯 High-Frequency Exam Questions

Trace through 4–6 steps of a sort by hand on a given array
Identify which algorithm produced a given intermediate state
Determine how many passes/comparisons have completed
Determine values of low, mid, high in binary search
Choose the most efficient algorithm for a described scenario
Explain why binary search fails on an unsorted array

⚠️ Common Traps

Binary search on unsorted data — will give wrong results, not an error
Selection sort "looks done early" — it still completes all comparisons even if array is already sorted
Off-by-one in binary search — remember mid = (low + high) / 2 uses integer division
Merge sort space — it needs O(n) extra space; AP exam may ask about memory usage
Return value of -1 — both search algorithms return -1 (not throw an exception) when not found
Insertion vs Selection trace — they look similar early on; count swaps to distinguish them

💡 Quick-Identification Cheat Sheet

Given an intermediate array state, identify the algorithm:

Original:  [5, 2, 8, 1, 9, 3]

After 2 passes of Selection Sort:
  [1, 2, 8, 5, 9, 3]   ← smallest 2 values locked at front

After 2 passes of Insertion Sort:
  [2, 5, 8, 1, 9, 3]   ← first 3 items sorted among themselves

Merge Sort intermediate (after merging pairs):
  [2, 5 | 1, 8 | 3, 9]  ← sorted pairs (not globally sorted yet)
      

📝 ArrayLists vs Arrays

The AP exam uses both. Searching and sorting work the same way conceptually, but syntax differs:

// Accessing elements:
arr[i]          // array
list.get(i)     // ArrayList

// Length/size:
arr.length      // array (no parentheses!)
list.size()    // ArrayList (with parentheses!)

// Setting values:
arr[i] = x;           // array
list.set(i, x);     // ArrayList
      