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.

Recursive searching and sorting appears in multiple-choice questions where you read code and decide what it returns or does, and binary search or merge sort may be shown in either recursive or loop form. You may also be asked what must be true for an algorithm to work, such as data being sorted before a binary search runs.

How Binary Search and Merge Sort Work

• 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.

Tracing Recursive Search and Sort Code

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. Tracing a few inputs usually reveals the method's overall purpose, because you can see the pattern in what each call returns.

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

• Misconception: Binary search works on unsorted data.
  Actually: 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.
• Misconception: Recursion makes algorithms faster.
  Actually: 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.
• Misconception: A recursive method does not need a base case.
  Actually: 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.
• Misconception: Merge sort sorts while splitting.
  Actually: 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.
• Misconception: The midpoint can be a fractional index.
  Actually: The midpoint uses integer division, so (left + right) / 2 and left + (right - left) / 2 both round down. Do not expect a fractional middle index.
• Misconception: For this course, you are writing recursive algorithms from scratch.
  Actually: 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