---
title: "AP Computer Science A 4.17: Recursive Searching and Sorting"
description: "Review AP Computer Science A 4.17, including recursive searching, recursive sorting, binary search, merge sort, tracing recursive algorithms, Strings, arrays, ArrayLists, sorted-data preconditions, each binary search iteration, merge sort splitting and merging, and exam scope limits."
canonical: "https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr"
type: "study-guide"
subject: "AP Computer Science A"
unit: "Unit 4 – Data Collections"
lastUpdated: "2026-06-07"
---

# AP Computer Science A 4.17: Recursive Searching and Sorting

## Summary

Review AP Computer Science A 4.17, including recursive searching, recursive sorting, binary search, merge sort, tracing recursive algorithms, Strings, arrays, ArrayLists, sorted-data preconditions, each binary search iteration, merge sort splitting and merging, and exam scope limits.

## Guide

## TLDR
Recursive searching and sorting in [AP Computer Science A](/ap-comp-sci-a "fv-autolink") focuses on three [algorithms](/ap-comp-sci-a/key-terms/algorithm "fv-autolink"): 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.

## 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](/ap-comp-sci-a/unit-4/recursion/study-guide/p4D3YegZCLwQ3KJVvsd4 "fv-autolink") that walks through a String, array, or [ArrayList](/ap-comp-sci-a/unit-4/developing-algorithms-using-arraylists/study-guide/MKbteieYvLOpWIwfqiND "fv-autolink") 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](/ap-comp-sci-a/unit-1/documentation-with-comments/study-guide/scrDad77j4e5vwrFab5J "fv-autolink") 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](/ap-comp-sci-a/key-terms/traverse "fv-autolink") 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](/ap-comp-sci-a/key-terms/linear-search "fv-autolink") 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](/ap-comp-sci-a/key-terms/tracing "fv-autolink") 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](/ap-comp-sci-a/key-terms/loop "fv-autolink") [iteration](/ap-comp-sci-a/unit-2/while-loops/study-guide/7qGsGOh1UKALAWpJhZOi "fv-autolink") 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](/ap-comp-sci-a/key-terms/integer-division "fv-autolink"), 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](/ap-comp-sci-a/unit-1/why-programming-why-java/study-guide/lVK6rmrBuug17i1Hna9z "fv-autolink") is the same idea as binary search and merge sort: handle a small piece now, then call the [method](/ap-comp-sci-a/unit-3/abstraction-and-program-design/study-guide/o9VgVeIpKRYZ7N7rXfUz "fv-autolink") 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](/ap-comp-sci-a/key-terms/parameter "fv-autolink") 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](/ap-comp-sci-a/unit-1/14-assignment-statement-input/study-guide/compoundassignment "fv-autolink") 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](/ap-comp-sci-a/unit-4/introduction-to-using-data-sets/study-guide/fq4I4p0XINBBV56xQfTx "fv-autolink") of `left`, `right`, and `mid` for each step. Confirm the array is sorted before you trust any binary search result. After each comparison, [update](/ap-comp-sci-a/unit-2/for-loops/study-guide/DJuLxKz6SiSAX2cEVmCt "fv-autolink") 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](/ap-comp-sci-a/key-terms/bounds "fv-autolink") 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](/ap-comp-sci-a/unit-2/algorithms-with-selection-and-repetition/study-guide/42crNSZyW8IRsntk9IHe "fv-autolink").
- 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](/ap-comp-sci-a/key-terms/index "fv-autolink").
- 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](/ap-comp-sci-a/unit-4/traversing-arrays/study-guide/kRcOqfawCcBz6gcT646t)
- [4.5 Developing Algorithms Using Arrays](/ap-comp-sci-a/unit-4/developing-algorithms-using-arrays/study-guide/c6dpJfmjG7oVFDqnXFAk)
- [4.1 Ethical and Social Implications](/ap-comp-sci-a/unit-4/ethical-and-social-implications/study-guide/iec7yzDQ2qENx5UAdiPJ)
- [4.11 2D Arrays](/ap-comp-sci-a/unit-4/2d-arrays/study-guide/5WDx6ZFeWhx2aVuiZI6R)
- [4.13 Implementing 2D Array Algorithms](/ap-comp-sci-a/unit-4/implementing-2d-array-algorithms/study-guide/9ucC5cB6ffrLnA4b3FU3)
- [4.16 Recursion](/ap-comp-sci-a/unit-4/recursion/study-guide/p4D3YegZCLwQ3KJVvsd4)

## Vocabulary

- **ArrayList**: A resizable array implementation in Java that can dynamically grow or shrink to store a collection of objects.
- **ArrayList objects**: Resizable collections in Java that can dynamically grow or shrink and can be traversed recursively.
- **String objects**: Data structures in Java that represent sequences of characters and can be traversed recursively.
- **array**: A data structure that stores a fixed-size collection of elements of the same type in contiguous memory locations, accessed by index.
- **binary search algorithm**: A search algorithm that finds a target value in a sorted collection by repeatedly dividing the search space in half, eliminating half of the remaining elements with each iteration.
- **iteration**: A form of repetition in which code is executed zero or more times based on a condition.
- **iteratively**: A method of solving a problem by repeating a set of instructions in a loop rather than through recursive function calls.
- **linear search**: A search algorithm that examines each element in a collection sequentially from the beginning until the target value is found or the end is reached.
- **merge sort**: A recursive sorting algorithm that divides an array into smaller subarrays, sorts them, and then merges them back together in sorted order.
- **recursion**: A programming technique where a function calls itself to solve a problem by breaking it into smaller, similar subproblems.
- **recursive algorithms**: Algorithms that solve problems by having a function call itself with modified parameters until reaching a base case.
- **recursive call**: An instance where a method invokes itself as part of its execution.
- **recursive sorting algorithm**: A sorting algorithm that uses recursion to divide and organize elements in a collection.
- **recursively**: A method of solving a problem by having a function call itself with modified parameters until a base case is reached.
- **sorted order**: A requirement for binary search in which elements in a collection are arranged in a specific sequence, typically in ascending or descending order.
- **subarray**: A contiguous portion of an array.
- **traverse**: To visit each element in a data structure (such as a string, array, or ArrayList) in a systematic way, often using recursion.

## FAQs

### What is recursive searching in AP Computer Science A?

Recursive searching uses a method that calls itself to look through a String, array, or ArrayList. For Topic 4.17, the main recursive search algorithm to know is binary search on sorted data.

### What is the precondition for binary search?

Binary search requires the collection to be sorted before the search begins. If the data is not sorted, eliminating half the collection each step is not logically valid.

### How does binary search work?

Binary search checks the middle item of a sorted array or ArrayList, then eliminates the half that cannot contain the target. It repeats until the target is found or no possible elements remain.

### Why is binary search usually faster than linear search?

Binary search usually runs faster on large sorted collections because each step removes about half of the remaining search space, while linear search checks items one at a time.

### What is merge sort in AP Computer Science A?

Merge sort is a recursive sorting algorithm that splits a collection into smaller parts until each part has one element, then merges the sorted parts back together in order.

### What sorting and searching algorithms are in AP CSA scope?

For AP CSA, linear search, binary search, selection sort, insertion sort, and merge sort are in scope. Search algorithms beyond linear and binary search, and sorting algorithms beyond selection, insertion, and merge sort, are outside the exam scope.

## Structured Data

```json
{"@context":"https://schema.org","@type":"FAQPage","inLanguage":"en","mainEntity":[{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr#what-is-recursive-searching-in-ap-computer-science-a","name":"What is recursive searching in AP Computer Science A?","acceptedAnswer":{"@type":"Answer","text":"Recursive searching uses a method that calls itself to look through a String, array, or ArrayList. For Topic 4.17, the main recursive search algorithm to know is binary search on sorted data."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr#what-is-the-precondition-for-binary-search","name":"What is the precondition for binary search?","acceptedAnswer":{"@type":"Answer","text":"Binary search requires the collection to be sorted before the search begins. If the data is not sorted, eliminating half the collection each step is not logically valid."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr#how-does-binary-search-work","name":"How does binary search work?","acceptedAnswer":{"@type":"Answer","text":"Binary search checks the middle item of a sorted array or ArrayList, then eliminates the half that cannot contain the target. It repeats until the target is found or no possible elements remain."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr#why-is-binary-search-usually-faster-than-linear-search","name":"Why is binary search usually faster than linear search?","acceptedAnswer":{"@type":"Answer","text":"Binary search usually runs faster on large sorted collections because each step removes about half of the remaining search space, while linear search checks items one at a time."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr#what-is-merge-sort-in-ap-computer-science-a","name":"What is merge sort in AP Computer Science A?","acceptedAnswer":{"@type":"Answer","text":"Merge sort is a recursive sorting algorithm that splits a collection into smaller parts until each part has one element, then merges the sorted parts back together in order."}},{"@type":"Question","@id":"https://fiveable.me/ap-comp-sci-a/unit-4/recursive-searching-and-sorting/study-guide/tP6n1uldmjMrgteAVspr#what-sorting-and-searching-algorithms-are-in-ap-csa-scope","name":"What sorting and searching algorithms are in AP CSA scope?","acceptedAnswer":{"@type":"Answer","text":"For AP CSA, linear search, binary search, selection sort, insertion sort, and merge sort are in scope. Search algorithms beyond linear and binary search, and sorting algorithms beyond selection, insertion, and merge sort, are outside the exam scope."}}]}
```