4.17 — Recursive Searching and Sorting

AP CSA · Unit 4: Data Collections

How can repeatedly solving a smaller problem help us search a sorted collection or put an unsorted collection in order?

Learning targets

Trace recursion over Strings, arrays, and ArrayLists; track the bounds of recursive binary search; and show both the splitting and merging stages of merge sort.

Before you start: Topic 4.16 recursion (base cases, recursive calls, returning to the caller), array indexes, ArrayList size()/get(), and comparison-based searching/sorting.

Try it: Predict the answer, record your work in your notes, and compare with a partner. Open each answer reveal after attempting the activity.

Your mission and learning path

You manage club event tickets. Search sorted ticket IDs to find a guest, and trace merge sort to organize an unsorted delivery.

Start with your experience: When a recursive call returns, what work is still waiting in its caller? Tell a partner what you expect before running anything.

Success looks like: You trace String/collection recursion, list binary-search bounds including an empty range, and show every merge without losing duplicates.

Learning design step	What you do	Evidence you keep
Understand the learner	Compare your prediction with a partner’s. Name what feels confusing.	One question in your notes
Define the goal	Read the success criteria and pick the skill you need to practice.	A specific goal
Try a small solution	Run an example, change one input, and predict the effect.	Before/after output
Test your idea	Attempt the popcorn task, then use the homework checks.	Expected versus actual results
Get feedback and revise	Have a partner try one new input. Explain and fix any mismatch.	One comment, your change, and the rerun

Suggested pace: 5 minutes to predict, 15 to explore, 10 for partner practice, and 5 for the exit ticket; finish the homework afterward.

Using the runners: Click Run below a challenge. Each editor is a separate complete Java program; it does not remember variables from another editor. Edit the code, then run again. Use Copy Code to keep your work. In a Java notebook, keep the final ClassName.main(null); call; in a .java file, remove that final call and run the class normally.

1. Warm-up: calls go down, returns come back

public static String reverse(String word) {
    if (word.length() <= 1) {
        return word;
    }
    return reverse(word.substring(1)) + word.substring(0, 1);
}

Predict: What does reverse("JAVA") return? What is waiting to happen while each recursive call runs?

Fill in the missing returns:

reverse("JAVA") = reverse("AVA") + "J"
reverse("AVA")  = reverse("VA")  + "A"
reverse("VA")   = reverse("A")   + "V"
reverse("A")    = ?

Returning upward: "A" -> ? -> ? -> ?

Check your reasoning

reverse("A") returns "A". Returning upward produces "AV", then "AVA", then "AVAJ".

Each caller waits to append its first character until the smaller call has returned. The problem shrinks because substring(1) removes the first character. Empty and one-character Strings reach the base case immediately.

Partner variation: Move the first character before the recursive call in the returned expression. Predict the result before tracing: word.substring(0, 1) + reverse(word.substring(1)) would preserve the original order.

2. Recursion over arrays and ArrayLists

An index can describe the part of a collection still to process.

// Precondition: values is nonnull and 0 <= index <= values.length.
public static int sumFrom(int[] values, int index) {
    if (index == values.length) {
        return 0;
    }
    return values[index] + sumFrom(values, index + 1);
}

For int[] values = {4, 1, 3};, complete this trace of sumFrom(values, 0):

index	Pending calculation	Returned value
0	`4 + sumFrom(values, 1)`	…
1	`1 + sumFrom(values, 2)`	…
2	`3 + sumFrom(values, 3)`	…
3	Base case	…

Now consider an ArrayList method. Add import java.util.ArrayList; above the surrounding class if running it.

// Precondition: words is nonnull, contains no null elements,
// and 0 <= index <= words.size().
public static int countLong(ArrayList<String> words, int index) {
    if (index == words.size()) {
        return 0;
    }
    int current = 0;
    if (words.get(index).length() >= 4) {
        current = 1;
    }
    return current + countLong(words, index + 1);
}

Think-pair-share: For a list containing "cat", "java", "loops", what does countLong(words, 0) return? What replaces array .length and [index] in the list version?

Check your reasoning

The array returns are 0 at index 3, then 3, 4, and finally 8 at index 0. The ArrayList result is 2 because "java" and "loops" qualify.

ArrayList uses .size() for the element count and .get(index) for indexed access. Both methods must check the base case before accessing an element. An empty collection called with index 0 returns 0.

3. Binary search: keep only the possible region

Start with this ascending sorted array:

index:  0   1   2   3   4   5   6
value:  3   7  12  18  24  31  42

low and high are inclusive endpoints. Compare the target with the middle value:

Equal: return the middle index.
Smaller: continue strictly to the left of the middle.
Larger: continue strictly to the right of the middle.
No indexes remain (low > high): return -1.

Why sorted matters: Once we see 18, we can rule out the left side for target 31 because every value on that side is at most 18. That guarantee disappears in an unsorted array.

// Precondition: values is nonnull and sorted in ascending order.
// Initial call: binarySearch(values, target, 0, values.length - 1).
public static int binarySearch(int[] values, int target, int low, int high) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (values[mid] == target) {
        return mid;
    }
    if (target < values[mid]) {
        return binarySearch(values, target, low, mid - 1);
    }
    return binarySearch(values, target, mid + 1, high);
}

Integer division rounds down here because the difference is nonnegative. Each unsuccessful comparison removes the already-checked middle index. The base-case check occurs before indexing the array.

Think about it: Why do recursive calls need return? Each call must pass the found index or -1 back to its caller.

Predict, then inspect the trace

For target 31, expect middle indexes 3, 5 and result 5. For target 20, expect middle indexes 3, 5, 4, then an empty-range call and result -1. Read the printed bounds as evidence; do not count the empty-range call as an inspected element.

AP focus: trace and explain provided recursive algorithms. The complete merge-sort implementation below is a supplied experiment, not a requirement to write recursive methods from memory. Its Arrays.copyOfRange calls are setup for displaying the two halves.

Code Runner Challenge

Trace target 31 first; change it to 20 and include the empty-range call.

View IPYNB Source

// CODE_RUNNER: Trace target 31 first; change it to 20 and include the empty-range call.

public class TicketSearchLab {
public static int binarySearch(int[] ids, int target, int low, int high) {
        System.out.println("call low=" + low + ", high=" + high);
        if (low > high) { return -1; }
        int mid = low + (high - low) / 2;
        System.out.println("inspect index " + mid + ", value " + ids[mid]);
        if (ids[mid] == target) { return mid; }
        if (target < ids[mid]) { return binarySearch(ids, target, low, mid - 1); }
        return binarySearch(ids, target, mid + 1, high);
    }
    public static void main(String[] args) {
        int[] ids = {3, 7, 12, 18, 24, 31, 42};
        int target = 31;
        System.out.println("Result index: " + binarySearch(ids, target, 0, ids.length - 1));
    }
}
TicketSearchLab.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

4. Human binary search

Put the seven values on cards. With your group, assign one person to track low, another to track high, and a third to compute mid. Predict which cards you can discard after each comparison.

Round A: find 31

Call	low	high	mid	values[mid]	Next action
1	0	6	…	…	…
2	…	…	…	…	…

Round B: find 20

Start again from the full array. Continue until the method returns, including the final empty-range call.

Check both traces

Target 31:

Call	low	high	mid	values[mid]	Next action
1	0	6	3	18	Search indexes 4–6
2	4	6	5	31	Return index 5

Target 20:

Call	low	high	mid	values[mid]	Next action
1	0	6	3	18	Search indexes 4–6
2	4	6	5	31	Search index 4
3	4	4	4	24	Search indexes 4–3
4	4	3	Not computed	Not accessed	Return -1

Round B makes three middle-value inspections and four method calls, including the empty-range base case. Always state what you are counting.

Change one condition

If the array has duplicate targets, must this method return the first matching index?
If the array is empty, what happens on the initial call?
Is the recursive implementation the only way to perform binary search?

Check your reasoning

No. It returns a matching middle index, which need not be the first occurrence.
low = 0 and high = -1; the base case returns -1 without accessing an element.
No. A loop can update the same bounds iteratively.

Your response

My Round B trace:
Why the array must be sorted:
Why mid + 1 or mid - 1 makes progress:
Why three inspections can involve four calls:

5. Merge sort: splitting is only half the job

Binary search eliminates a region that cannot contain the target. Merge sort processes both halves and then combines their sorted results.

Use these cards: 8, 3, 6, 2, 7, 1, 5, 4.

Split phase

                 [8, 3, 6, 2, 7, 1, 5, 4]
                 /                       \
          [8, 3, 6, 2]                [7, 1, 5, 4]
          /          \                /          \
       [8, 3]      [6, 2]          [7, 1]      [5, 4]
       /   \       /   \           /   \       /   \
      [8]  [3]    [6]  [2]         [7]  [1]    [5]  [4]

A zero- or one-element collection is already sorted. Splitting alone does not rearrange the values into order.

Merge phase — your turn

Fill each blank before checking:

[8] + [3] -> [____]        [6] + [2] -> [____]
[7] + [1] -> [____]        [5] + [4] -> [____]

[3, 8] + [2, 6] -> [____________]
[1, 7] + [4, 5] -> [____________]

[2, 3, 6, 8] + [1, 4, 5, 7] -> [________________________]

At each merge, compare the first unused element of each sorted half. Take the smaller one and advance only that half’s pointer. When a half runs out, append the other half’s remaining elements.

Check the merge stages

Pairs: [3, 8], [2, 6], [1, 7], [4, 5].

Groups of four: [2, 3, 6, 8] and [1, 4, 5, 7].

Final result: [1, 2, 3, 4, 5, 6, 7, 8].

The diagram groups results of the same size. A typical recursive implementation finishes the left half before recursively sorting the right half; it does not necessarily execute all same-sized merges together.

6. Partner activity: merge with two pointers

Partner A manages [2, 3, 6, 8]; partner B manages [1, 4, 5, 7]. Take turns announcing the comparison and moving one pointer.

Step	Next left value	Next right value	Value appended
1	2	1	…
2	2	4	…
3	…	…	…

Challenge: Count only comparisons between two available values, not loop-condition checks. How many such comparisons occur in this final merge?

Check the complete merge trace

Step	Left	Right	Appended
1	2	1	1
2	2	4	2
3	3	4	3
4	6	4	4
5	6	5	5
6	6	7	6
7	8	7	7
8	8	Exhausted	8

There are 7 comparisons between available values. Appending the leftover 8 needs no comparison against a right-side value.

Read the merge helper

This method combines two already-sorted arrays into a new sorted array. It is the combine step, not a complete merge sort.

public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k] = left[i];
            i++;
        } else {
            result[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < left.length) {
        result[k] = left[i];
        i++;
        k++;
    }
    while (j < right.length) {
        result[k] = right[j];
        j++;
        k++;
    }
    return result;
}

Discuss: Why do we need both leftover loops? What would go wrong if the first loop used || instead of &&?

Check your reasoning

Either half can run out first. The leftover loops copy everything still unconsumed in the other half. With ||, the first loop could continue after one side runs out and attempt an invalid array access. The <= tie rule chooses the left element first when values are equal.

Code Runner Challenge

Predict each merged group for 9, 2, 6, 1; then try duplicate values.

View IPYNB Source

// CODE_RUNNER: Predict each merged group for 9, 2, 6, 1; then try duplicate values.
import java.util.Arrays;
public class TicketSortLab {
public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) { result[k++] = left[i++]; }
            else { result[k++] = right[j++]; }
        }
        while (i < left.length) { result[k++] = left[i++]; }
        while (j < right.length) { result[k++] = right[j++]; }
        return result;
    }
    // Supplied visualization code: trace it; you do not have to write it from memory.
    public static int[] mergeSort(int[] values) {
        if (values.length <= 1) { return values; }
        int mid = values.length / 2;
        int[] left = Arrays.copyOfRange(values, 0, mid);
        int[] right = Arrays.copyOfRange(values, mid, values.length);
        System.out.println("split " + Arrays.toString(values) + " -> "
            + Arrays.toString(left) + " | " + Arrays.toString(right));
        int[] result = merge(mergeSort(left), mergeSort(right));
        System.out.println("merge -> " + Arrays.toString(result));
        return result;
    }
    public static void main(String[] args) {
        int[] tickets = {9, 2, 6, 1};
        System.out.println("Sorted: " + Arrays.toString(mergeSort(tickets)));
    }
}
TicketSortLab.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

7. Compare the algorithms

Algorithm	Starting condition	What happens to the data?	How the work shrinks
Linear search	May be unsorted	Finds a match by inspection	Checks one more element at a time
Binary search	Sorted using the comparison order	Finds a matching index; does not sort	Continues in one half
Merge sort	May be unsorted	Produces sorted order	Sorts both halves, then merges

With 15 sorted elements, this binary-search implementation needs at most 4 middle-value inspections; a linear search may inspect all 15. Binary search’s benefit assumes the data is already sorted. Sorting an unsorted collection solely for one search adds work.

8. Popcorn hack: diagnose the recursion

A classmate changes the right-side binary-search call to:

return binarySearch(values, target, mid, high);

Use values = {3, 7} and target = 7.

Write low, high, and mid for the first two calls.
Explain why the range can fail to shrink.
Repair the call.
Design a missing-target test and show the expected result.

Reveal a solution after your trace

The first call has low = 0, high = 1, mid = 0. The faulty call repeats the same bounds: 0, 1, so mid remains 0. It keeps inspecting 3 and never reaches the 7; eventually Java exhausts its call stack.

Repair:

return binarySearch(values, target, mid + 1, high);

For a missing target such as 5, the repaired algorithm inspects index 0, then index 1, then reaches bounds 1, 0 and returns -1.

Merge-sort transfer challenge

Trace merge sort on [9, 2, 6, 1]. Show the singleton groups, sorted pairs, and final merge. Then repeat the merge step for sorted halves [2, 4] and [2, 3], preserving both copies of 2.

Check the transfer challenge

Singletons: [9], [2], [6], [1]. Sorted pairs: [2, 9], [1, 6]. Final merge: [1, 2, 6, 9].

Duplicate example: [2, 2, 3, 4]. Sorting retains duplicates; it does not remove them. The helper’s tie rule takes the left 2 first.

Your response

Faulty-call trace:
My repair and explanation:
Missing-target test and expected result:
Merge-sort split and merge stages:
My rule for recognizing a valid base case:

9. Exit ticket

Trace binary search for 12 in [3, 7, 12, 18, 24, 31, 42]. List middle indexes in order, then the returned index.
What happens when low > high? Is another middle element inspected?
Merge sorted halves [1, 5, 9] and [2, 4, 8].
Why does merge sort need a merge phase after splitting?
For the warm-up method, what does reverse("") return?

Exit-ticket key

Middle indexes 3, 1, 2; return 2.
The method returns -1 before computing or accessing another middle element.
[1, 2, 4, 5, 8, 9].
The split creates small subproblems but does not put values from different halves in order. Merging combines sorted halves into a larger sorted result.
The empty String; it already satisfies the base case.

Homework: ticket-desk trace report

Use the supplied search and sort methods. Before running, replace the six prediction values in main and write your supporting traces in your homework notebook. Do not rewrite the algorithms or change a prediction after seeing the output without recording why you revised it.

For target 12, list (low, high, mid) for every inspection and the returned index.
For missing target 20, include the final empty-range call; distinguish call count from inspection count.
Explain the empty search and empty sort results.
For [9, 2, 6, 1], draw the split groups and all three merged groups.
For [2, 4, 2, 3], keep both copies of 2 and show how the final merge preserves them.
Add a singleton or duplicate-target test. For duplicate targets, explain why binary search need not return the first matching index.

The supplied placeholder predictions produce FAIL, not a compiler error. Passing checks alone are insufficient: your trace and explanation are the homework. Recursive code writing is an optional extension.

Code Runner Challenge

Fill in the six predictions before running. Keep a paper trace to explain every answer.

View IPYNB Source

// CODE_RUNNER: Fill in the six predictions before running. Keep a paper trace to explain every answer.
import java.util.Arrays;
public class TicketHomework {
public static int binarySearch(int[] ids, int target, int low, int high) {
        System.out.println("call low=" + low + ", high=" + high);
        if (low > high) { return -1; }
        int mid = low + (high - low) / 2;
        System.out.println("inspect index " + mid + ", value " + ids[mid]);
        if (ids[mid] == target) { return mid; }
        if (target < ids[mid]) { return binarySearch(ids, target, low, mid - 1); }
        return binarySearch(ids, target, mid + 1, high);
    }
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) { result[k++] = left[i++]; }
            else { result[k++] = right[j++]; }
        }
        while (i < left.length) { result[k++] = left[i++]; }
        while (j < right.length) { result[k++] = right[j++]; }
        return result;
    }
    // Supplied visualization code: trace it; you do not have to write it from memory.
    public static int[] mergeSort(int[] values) {
        if (values.length <= 1) { return values; }
        int mid = values.length / 2;
        int[] left = Arrays.copyOfRange(values, 0, mid);
        int[] right = Arrays.copyOfRange(values, mid, values.length);
        System.out.println("split " + Arrays.toString(values) + " -> "
            + Arrays.toString(left) + " | " + Arrays.toString(right));
        int[] result = merge(mergeSort(left), mergeSort(right));
        System.out.println("merge -> " + Arrays.toString(result));
        return result;
    }
    public static void check(String label, String prediction, String actual) {
        System.out.println((prediction.equals(actual) ? "PASS" : "FAIL")
            + " " + label + ": predicted " + prediction + ", actual " + actual);
    }
    public static void main(String[] args) {
        // TODO: Replace only these predictions after tracing by hand.
        int predictedFound = -99;
        int predictedMissing = -99;
        int predictedEmpty = -99;
        String predictedSorted = "TODO";
        String predictedDuplicates = "TODO";
        String predictedEmptySort = "TODO";
        int[] ids = {3, 7, 12, 18, 24, 31, 42};
        check("find 12", "" + predictedFound, "" + binarySearch(ids, 12, 0, ids.length - 1));
        check("find 20", "" + predictedMissing, "" + binarySearch(ids, 20, 0, ids.length - 1));
        check("empty search", "" + predictedEmpty, "" + binarySearch(new int[] {}, 12, 0, -1));
        check("sort", predictedSorted, Arrays.toString(mergeSort(new int[] {9, 2, 6, 1})));
        check("duplicates", predictedDuplicates, Arrays.toString(mergeSort(new int[] {2, 4, 2, 3})));
        check("empty sort", predictedEmptySort, Arrays.toString(mergeSort(new int[] {})));
    }
}
TicketHomework.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Publish your homework and check it as a student

In your own portfolio, create _notebooks/homework/2026-09-21-4-17-homework.ipynb. Choose a Java kernel. Copy your completed homework runner into a code cell, including the imports, class, and final main(null) call.
Add a raw cell first with the template below. Replace your-github-id and Your Name; keep your own unique permalink.

---
layout: post
title: "4.17 Homework"
description: "My predictions, Java solution, test results, and revision."
author: Your Name
categories: [Java, Homework]
lesson_language: Java
codemirror: true
permalink: /homework/your-github-id/4-17/
---

Add Markdown sections named Prediction, Solution, Tests, and Feedback and revision. Keep the six original predictions, search/merge traces, actual outputs, and a brief explanation of any revised prediction.
Run all cells from a fresh kernel. Keep the printed output. Include the supplied checks and one test you designed, with expected and actual results. Fix failing checks before submitting.
Commit and publish in your portfolio. Open the published homework page and run its editor again. Check that the code, outputs/evidence, and your name are visible. If you get a 404, check the build and the exact permalink before submitting.
Use the lesson’s submission form when available: sign in, paste your published homework URL, and include the evidence below. If your class uses a different submission destination, use the one your teacher provides. Do not submit the lesson’s URL as your homework.

Lesson: 4.17
Homework URL:
Popcorn result:
Supplied checks passed / total:
My extra test: input / expected / actual
Partner feedback:
What I changed and the rerun result:

Self-check rubric (1 point): popcorn work with reasoning 0.2; completed homework and explanation 0.4; supplied tests plus your own boundary test 0.2; working published link and feedback/revision evidence 0.2. These are the lesson’s proposed criteria; follow any changes your teacher gives you.

If every check already passes, revise an explanation or add a stronger test after peer feedback. Report what actually happened; do not invent a peer review or a test result.

References and next steps

College Board AP Computer Science A Course and Exam Description, effective fall 2025 — Topic 4.17; use the topic heading to find the learning objectives and exam scope.
Oracle: Arrays — toString and copyOfRange used by the supplied trace programs.
Java lesson catalog — return to the class’s lesson collection.

Submit Assignment

Need to update a submission later? Open the submissions dashboard.