4.17 Recursive Searching and Sorting

TLDR

Recursive searching and sorting in AP Computer Science A focuses on three algorithms: recursive traversals of Strings, arrays, and ArrayLists; binary search, which repeatedly cuts a sorted collection in half; and merge sort, which splits a collection down to single elements and merges them back in order. On the exam you trace these algorithms and predict their output or behavior, not write them from scratch.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science A Exam

This topic shows up on the multiple-choice section, where you read recursive code and figure out what it returns or does. The skills being tested are describing the behavior of a code segment and identifying the conditions that must be true for an algorithm to work, like data being sorted before a binary search runs.

You should be able to:

• Trace a recursive method that walks through a String, array, or ArrayList and find its result.
• Follow each step of a binary search and name which half gets eliminated.
• Track how merge sort splits a collection and rebuilds it in sorted order.
• Recognize the precondition that data must be sorted before binary search can be used.

Binary search and merge sort both use recursion, but they can also be written with loops. The exam may show either version, so focus on the behavior rather than one fixed style.

Key Takeaways

• Recursion can traverse Strings, arrays, and ArrayLists by handling one piece at a time and calling itself on the rest, always with a base case to stop.
• Binary search only works on sorted data. It checks the middle, then eliminates half the collection each step until it finds the target or runs out of elements.
• Binary search is typically more efficient than linear search because it removes half the remaining elements per step instead of checking one at a time.
• Both binary search and merge sort can be written iteratively or recursively, so trace the logic, not the format.
• Merge sort repeatedly divides a collection until each subarray holds one element, then merges sorted subarrays back together in order.
• The exam tests recursion through tracing and predicting output, not through writing recursive code yourself.

Binary Search

Binary search finds a target in a sorted collection by repeatedly checking the middle element and discarding the half that cannot contain the target. Because each step removes half of what is left, it is typically much faster than linear search on large sorted data.

The two things you must remember:

• The data has to be sorted first. If it is not sorted, the result is not reliable.
• Each call or loop iteration eliminates half the remaining elements.

Here is a recursive version. Notice the base cases and the recursive cases.

</>Java
public static int binarySearch(int[] arr, int target, int left, int right) {
    // Base case: element not found
    if (left > right) {
        return -1;
    }

    // Calculate middle index (avoids overflow)
    int mid = left + (right - left) / 2;

    // Base case: found the target
    if (arr[mid] == target) {
        return mid;
    }

    // Recursive cases: search the appropriate half
    if (target < arr[mid]) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

Code Tracing

Walk through it with arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} and target = 13.

• left = 0, right = 9, mid = 4, arr[4] = 9. Since 13 > 9, search the right half: left = 5.
• left = 5, right = 9, mid = 7, arr[7] = 15. Since 13 < 15, search the left half: right = 6.
• left = 5, right = 6, mid = 5, arr[5] = 11. Since 13 > 11, search the right half: left = 6.
• left = 6, right = 6, mid = 6, arr[6] = 13. Match found, return 6.

When you trace binary search on the exam, write down left, right, and mid at each step. The midpoint formula left + (right - left) / 2 uses integer division, so it rounds down.

Binary search can also be written with a loop instead of recursion. The behavior is identical: check the middle, then move left or right to cut the range in half. Focus on which half survives each step.

Merge Sort

Merge sort is a recursive sorting algorithm built on divide and combine. It splits a collection in half over and over until each piece is a single element, then merges those pieces back together in sorted order.

The two phases:

• Divide: keep splitting the array at the midpoint until every subarray has one element. A single element is already sorted, which is the base case.
• Merge: combine two sorted subarrays into one sorted subarray by comparing their front elements and taking the smaller one each time.

</>Java
public static void mergeSort(int[] arr, int left, int right) {
    // Base case: single element or empty range is already sorted
    if (left >= right) {
        return;
    }

    // Divide: find the middle point
    int mid = left + (right - left) / 2;

    // solve: recursively sort both halves
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Combine: merge the sorted halves
    merge(arr, left, mid, right);
}

The merge step uses temporary arrays to hold the two halves while combining them:

</>Java
private static void merge(int[] arr, int left, int mid, int right) {
    int leftSize = mid - left + 1;
    int rightSize = right - mid;

    int[] leftArray = new int[leftSize];
    int[] rightArray = new int[rightSize];

    for (int i = 0; i < leftSize; i++) {
        leftArray[i] = arr[left + i];
    }
    for (int j = 0; j < rightSize; j++) {
        rightArray[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0;  // indices into the two halves
    int k = left;      // index into the merged result

    while (i < leftSize && j < rightSize) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    // Copy any remaining elements
    while (i < leftSize) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }
    while (j < rightSize) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

Code Tracing

Take {8, 3, 5, 1}.

• Split into {8, 3} and {5, 1}.
• Split {8, 3} into {8} and {3}. Merge them into {3, 8}.
• Split {5, 1} into {5} and {1}. Merge them into {1, 5}.
• Merge {3, 8} and {1, 5}: compare 3 and 1, take 1; compare 3 and 5, take 3; compare 8 and 5, take 5; take the remaining 8. Result: {1, 3, 5, 8}.

When you trace merge sort, draw the splitting as a tree going down, then build the sorted result coming back up. The splitting always reaches single elements before any real merging happens.

Recursive Traversals of Strings and Collections

Recursion can also walk through a String, array, or ArrayList one element at a time. The pattern is the same idea as binary search and merge sort: handle a small piece now, then call the method on the smaller remaining part, with a base case that stops the recursion.

A common example is processing the first character of a String, then recursing on the rest:

</>Java
public static int countChar(String s, char target) {
    // Base case: empty string has nothing to count
    if (s.length() == 0) {
        return 0;
    }

    // Check the first character, then recurse on the rest
    int countRest = countChar(s.substring(1), target);
    if (s.charAt(0) == target) {
        return 1 + countRest;
    } else {
        return countRest;
    }
}

When tracing this kind of method, track how the parameter shrinks on each call and remember that each call has its own copy of the parameters. The base case is what eventually stops the chain of calls.

How to Use This on the AP Computer Science A Exam

Code Tracing

For any recursive method, plug in a specific input and follow it call by call. Write down the parameters for each call and what each call returns. Because a recursive method gives one result per input, tracing a few inputs usually reveals the method's overall purpose.

Binary Search Steps

Keep a small table of left, right, and mid for each step. Confirm the array is sorted before you trust any binary search result. After each comparison, update either left or right and recompute mid.

Merge Sort Steps

Sketch the splits as a downward tree until every piece is one element, then merge upward. The hard part on the exam is usually the merge: compare the front elements of two sorted pieces and repeatedly take the smaller one.

Common Trap

Watch for off-by-one mistakes. In binary search, the new bounds are mid - 1 and mid + 1, not mid. In merge sort, the left half runs through mid and the right half starts at mid + 1.

Common Misconceptions

• Binary search does not work on unsorted data. If the collection is not sorted, the algorithm can skip past the target and return the wrong answer.
• Recursion is not magic speed. Binary search and merge sort can be written with loops and behave the same way; recursion is just another form of repetition.
• A recursive method needs a base case. Without one, the calls never stop and the program fails. Every recursive method here has at least one base case and at least one recursive call.
• Merge sort does not sort while splitting. The real ordering happens during the merge steps as pieces come back together, not while the array is being divided.
• The midpoint uses integer division, so (left + right) / 2 and left + (right - left) / 2 both round down. Do not expect a fractional middle index.
• For this course, you are tracing and predicting the behavior of recursive search and sort code, not writing recursive algorithms from scratch.

Related AP Computer Science A Guides

• 4.4 Traversing Arrays
• 4.5 Developing Algorithms Using Arrays
• 4.1 Ethical and Social Implications
• 4.11 2D Arrays
• 4.13 Implementing 2D Array Algorithms
• 4.16 Recursion