AP Computer Science a Quiz: Recursive Searching And Sorting

What this quiz covers

This quiz focuses on Recursive Searching And Sorting, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science a.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

public class Searcher {
    public static int binarySearch(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (target < nums[mid]) {
            return binarySearch(nums, target, low, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, high);
        }
    }
}

1. $O(n)$ because it may check every index once.
2. $O(1)$ because it always checks the middle element.
3. $O(\log n)$ because it halves the search interval each call. (correct answer)
4. $O(n \log n)$ because it sorts while searching.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing binary search's time complexity. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the binary search algorithm halves the search interval with each recursive call by adjusting either the low or high boundary based on the comparison with the middle element. Choice C is correct because binary search has O(log n) time complexity since each recursive call eliminates half of the remaining elements, requiring at most log₂(n) comparisons to find the target or determine it's not present. Choice A is incorrect because O(n) would mean checking every element, which only happens in the worst case of linear search, not binary search's efficient halving strategy. To help students: Show how a 16-element array requires at most 4 comparisons (log₂16 = 4). Create a table showing how the search space shrinks: 16→8→4→2→1, demonstrating the logarithmic pattern.

Question 2

public class Sorter {
    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private static void merge(int[] nums, 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) {
            temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        for (int t = 0; t < temp.length; t++) nums[left + t] = temp[t];
    }
}

1. $O(\log n)$ because it only splits the array.
2. $O(n)$ because each element moves at most once.
3. $O(n^2)$ because it compares every pair of elements.
4. $O(n \log n)$ because it splits and merges across levels. (correct answer)

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of recursive merge sort. Understanding merge sort's complexity requires analyzing both the recursive splitting and the merging phases. The algorithm creates a recursion tree with log n levels (since we halve the problem size at each level), and at each level, the merge operations collectively process all n elements. Choice D is correct because merge sort has O(n log n) time complexity: there are O(log n) levels in the recursion tree, and each level requires O(n) work to merge all segments at that level. Choice C is incorrect because O(n²) would imply nested loops comparing every pair, but merge sort's divide-and-conquer approach avoids this quadratic behavior. To help students: Draw the recursion tree showing how n elements are split into n single-element arrays across log n levels. Calculate the total work at each level (always n) and multiply by the number of levels (log n) to get n log n total operations.

Question 3

public static void mergeSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

1. $O(n)$ because each element is visited once
2. $O(n^2)$ because it compares every pair of elements
3. $O(n \log n)$ because it splits and merges each level (correct answer)
4. $O(\log n)$ because it halves the array each call

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of merge sort. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, merge sort divides the array in half at each level (creating log n levels) and performs O(n) work at each level to merge the subarrays. Choice C is correct because the algorithm has O(log n) recursive levels, and at each level, all n elements are processed during the merge operations, resulting in O(n log n) total time complexity. Choice D is incorrect because while there are O(log n) levels of recursion, it ignores the O(n) work done at each level for merging. To help students: Draw the recursion tree showing log n levels with n total elements processed at each level. Emphasize that time complexity analysis must consider both the depth of recursion and the work done at each level.

Question 4

// Merge sort: split, sort halves recursively, then merge
public static void mergeSort(int[] nums, int left, int right) {
    // Base case: one element (already sorted)
    if (left >= right) {
        return;
    }

    int mid = (left + right) / 2;

    // Recursive calls: sort left half and right half
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    // Merge step: combine two sorted halves
    merge(nums, left, mid, right);
}

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

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

    for (int t = 0; t < temp.length; t++) {
        nums[left + t] = temp[t];
    }
}

1. It swaps adjacent elements until the array is sorted
2. It repeatedly splits into halves, then merges sorted subarrays (correct answer)
3. It chooses a pivot and partitions in place each call
4. It searches for the target value by halving the range

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how merge sort processes arrays recursively. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the merge sort algorithm divides the array into two halves at each recursive level, sorts each half independently through recursive calls, then merges the sorted halves back together. Choice B is correct because it accurately describes the divide-and-conquer approach: the array is repeatedly split into halves until single elements remain, then sorted subarrays are merged bottom-up. Choice A is incorrect because it describes bubble sort's behavior of swapping adjacent elements, not merge sort's divide-and-conquer strategy. To help students: Use visual diagrams showing the recursive tree structure of merge sort. Trace through a small array example showing how it splits down to single elements then merges back up in sorted order.

Question 5

public class MathUtil {
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

1. It adds n to factorial(n - 1) until n becomes 0.
2. It multiplies n by factorial(n - 1) until reaching the base case. (correct answer)
3. It multiplies n by factorial(n + 1) until n becomes 4.
4. It returns 0 when n is 1, then multiplies back up.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how recursive factorial builds its result. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the factorial method demonstrates how factorial(4) computes 4! by multiplying 4 by factorial(3), which in turn multiplies 3 by factorial(2), and so on until reaching the base case. Choice B is correct because it accurately describes the recursive process: each call multiplies n by the factorial of (n-1), continuing until n reaches 0 (the base case), at which point the recursion unwinds and multiplications occur. Choice A is incorrect because it describes addition rather than multiplication; factorial uses the formula n! = n × (n-1)!, not n! = n + (n-1)!. To help students: Draw the call stack for factorial(4) showing how it builds up: 4×(3×(2×(1×(0!)))) = 4×(3×(2×(1×1))) = 24. Emphasize the multiplication operation and how results propagate back up the call stack.

Question 6

public class Searcher {
    public static int binarySearch(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (target < nums[mid]) {
            return binarySearch(nums, target, low, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, high);
        }
    }
}

1. $O(n)$ because it may check every element.
2. $O(n \log n)$ because it divides and then merges.
3. $O(1)$ because it uses constant extra variables.
4. $O(\log n)$ because each call halves the interval. (correct answer)

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of recursive binary search. Time complexity analysis requires understanding how the number of operations grows with input size n. In binary search, each recursive call eliminates half of the remaining elements by choosing to search either the left or right half based on the comparison with the middle element. Choice D is correct because the algorithm halves the search interval with each recursive call, resulting in at most log₂(n) recursive calls before the base case is reached, giving O(log n) time complexity. Choice A is incorrect because O(n) would mean checking every element, which contradicts binary search's divide-and-conquer approach that skips half the elements at each step. To help students: Draw recursion trees showing how the problem size decreases from n to n/2 to n/4, etc. Emphasize that the number of times you can divide n by 2 until reaching 1 is log₂(n), which is the maximum recursion depth.

Question 7

public class Sorter {
    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;

        // Recursive calls sort subarrays
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // Merge combines two sorted subarrays
        merge(nums, left, mid, right);
    }

    private static void merge(int[] nums, 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) {
            temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        for (int t = 0; t < temp.length; t++) nums[left + t] = temp[t];
    }
}

1. Each call reverses its segment, so merges become sorted automatically.
2. Each call sorts both halves, then merge combines them into one sorted segment. (correct answer)
3. Each call searches for the minimum element and swaps it into place.
4. Each call sorts only the left half, and the right half stays unchanged.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding the divide-and-conquer strategy in merge sort. Merge sort works by recursively breaking down the problem into smaller subproblems until they're trivial to solve, then combining solutions. In this implementation, each call to mergeSort first recursively sorts the left half (left to mid), then the right half (mid+1 to right), and finally merges these two sorted halves into one sorted segment. Choice B is correct because it accurately describes the two-phase process: recursive calls sort both halves independently, then the merge function combines these sorted halves while maintaining order. Choice D is incorrect because merge sort must sort both halves, not just the left half, to ensure the entire array becomes sorted. To help students: Use tree diagrams to visualize the recursive decomposition and subsequent merging phases. Emphasize that the 'magic' happens in the merge step, which combines two sorted sequences into one larger sorted sequence.

Question 8

public class Sorter {
    // Sorts nums[left..right] by recursively sorting subranges
    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;

        // Recursive step: split into two index ranges
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // Merge step combines sorted ranges
        merge(nums, left, mid, right);
    }

    private static void merge(int[] nums, 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) {
            temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        for (int t = 0; t < temp.length; t++) nums[left + t] = temp[t];
    }
}

1. It copies the entire array into two new arrays at each call.
2. It updates left/right to work on smaller index ranges. (correct answer)
3. It removes elements from the array so recursion terminates sooner.
4. It uses the same mid value for all recursive calls.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on how merge sort manages array segments during recursion. Efficient sorting algorithms minimize memory usage by working with index ranges rather than creating array copies. In this merge sort implementation, the original array is passed to all recursive calls, but each call operates on a specific segment defined by the left and right indices, effectively dividing the work without copying data. Choice B is correct because it accurately describes how the algorithm updates the left and right parameters to define progressively smaller index ranges, allowing each recursive call to focus on its assigned portion of the array. Choice A is incorrect because copying the entire array at each recursive call would be extremely inefficient and unnecessary when index boundaries suffice. To help students: Use diagrams showing the same array with different colored segments representing the ranges each recursive call handles. Emphasize that changing indices is much more efficient than copying array elements, especially for large datasets.

Question 9

public class Sorter {
    public static void mergeSort(int[] nums, int left, int right) {
        // Base case: one element (or empty) segment is already sorted
        if (left >= right) {
            return;
        }

        int mid = (left + right) / 2;

        // Recursive step: sort both halves
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // Merge sorted halves
        merge(nums, left, mid, right);
    }

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

        // Merge elements in sorted order
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        // Copy back
        for (int t = 0; t < temp.length; t++) {
            nums[left + t] = temp[t];
        }
    }
}

1. When left > right, return immediately.
2. When mid == 0, return immediately.
3. When left >= right, return immediately. (correct answer)
4. When the array is in descending order, return immediately.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying the base case in recursive merge sort. The base case in merge sort represents when a segment is so small that it's already sorted by definition. In this implementation, the condition if (left >= right) serves as the base case, stopping recursion when the segment has one element (left == right) or is empty (left > right). Choice C is correct because when left >= right, the segment contains at most one element, which is inherently sorted and requires no further splitting or merging. Choice A is incorrect because it only covers the empty segment case (left > right) but misses the single-element case (left == right), which is also a valid base case. To help students: Explain that arrays of size 0 or 1 are sorted by definition. Trace through examples showing how recursive calls eventually reach segments where left equals right, representing single elements that form the building blocks for merging.

Question 10

public class Searcher {
    // Returns index of target in sorted array, or -1 if not found
    public static int binarySearch(int[] nums, int target, int low, int high) {
        // Base case: interval is empty
        if (low > high) {
            return -1;
        }

        int mid = (low + high) / 2;

        // Found target
        if (nums[mid] == target) {
            return mid;
        }

        // Recursive step: search one half
        if (target < nums[mid]) {
            return binarySearch(nums, target, low, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, high);
        }
    }
}

1. When low == high, return -1.
2. When low > high, return -1. (correct answer)
3. When nums[mid] != target, return -1.
4. When mid == 0, return -1.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding the base case in recursive binary search. In recursive algorithms, the base case is the condition that stops the recursion and prevents infinite calls. In this binary search implementation, the base case if (low > high) occurs when the search interval becomes invalid (empty), meaning the target cannot be found in the remaining search space. Choice B is correct because when low > high, it indicates that the search boundaries have crossed, which happens after repeatedly narrowing the search interval without finding the target. Choice A is incorrect because low == high represents a valid single-element interval that still needs to be checked. To help students: Emphasize that base cases prevent infinite recursion and represent the simplest form of the problem. Practice tracing through examples where the target is not found, observing how the interval shrinks until low exceeds high.

Question 11

public class Searcher {
    // Example call: binarySearch(new int[]{2,4,7,9,12,15}, 9, 0, 5)
    public static int binarySearch(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }

        int mid = (low + high) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        // Recursive step: discard half the array
        if (target < nums[mid]) {
            return binarySearch(nums, target, low, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, high);
        }
    }
}

1. It increments low by 1 until target is found.
2. It swaps elements so the target moves toward the middle.
3. It recurses on only one half by updating low or high past mid. (correct answer)
4. It always searches both halves and returns the smaller index.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on how recursive binary search reduces the problem size. Binary search achieves efficiency by eliminating half of the remaining elements with each recursive call, leveraging the sorted nature of the array. In this implementation, after comparing the target with the middle element, the algorithm makes a recursive call with adjusted boundaries: either binarySearch(nums, target, low, mid - 1) for the left half or binarySearch(nums, target, mid + 1, high) for the right half. Choice C is correct because it accurately describes how the recursive call updates either the low or high parameter to exclude the already-checked middle element and its corresponding half. Choice A is incorrect because binary search doesn't increment linearly through elements; it jumps to the middle of intervals. To help students: Use visual diagrams showing how the search interval shrinks with each recursive call. Trace through specific examples showing how low and high boundaries change, emphasizing that we always exclude the middle element in the next recursive call.

Question 12

public class Searcher {
    // Searches within nums[low..high] without creating new arrays
    public static int binarySearch(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (target < nums[mid]) {
            return binarySearch(nums, target, low, mid - 1);
        } else {
            return binarySearch(nums, target, mid + 1, high);
        }
    }
}

1. It creates a new subarray for each recursive call.
2. It sorts the array again before each recursive call.
3. It searches using the same array but changes low and high. (correct answer)
4. It reverses the array when target is smaller than nums[mid].

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how recursive binary search manages memory and array access. Efficient recursive algorithms often work with the original data structure using index boundaries rather than creating copies. In this implementation, the same array reference nums is passed to each recursive call, but the search boundaries are adjusted through the low and high parameters, effectively limiting which portion of the array is being searched. Choice C is correct because it accurately describes that the algorithm reuses the same array throughout all recursive calls while changing only the index boundaries to focus on different segments. Choice A is incorrect because creating new subarrays would be inefficient and unnecessary, as we can simply adjust indices to work with different portions of the original array. To help students: Emphasize the difference between passing array references versus creating array copies. Use memory diagrams to show how all recursive calls share the same array in memory, with only the low and high values on the call stack changing.

Question 13

public class MathUtil {
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        }
        // Recursive call multiplies by the factorial of the smaller problem
        return n * factorial(n - 1);
    }
}

1. It adds n repeatedly until reaching 0.
2. It multiplies n by the result of factorial(n - 1) until the base case. (correct answer)
3. It divides n by 2 each call until reaching 1.
4. It sorts numbers from 1 to n and returns the last value.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how recursive calls build up the final result. Recursive factorial demonstrates how solutions to smaller problems combine to solve larger ones. In this implementation, each recursive call computes n! by multiplying n with the factorial of (n-1), following the mathematical definition n! = n × (n-1)!. Choice B is correct because it accurately describes the recursive process: each call multiplies the current value n by the result of factorial(n-1), continuing until reaching the base case where factorial(0) returns 1. Choice A is incorrect because factorial involves multiplication, not addition, and the recursive structure multiplies values rather than adding them. To help students: Trace through a concrete example like factorial(4), showing the call stack and how return values propagate back up. Emphasize how each recursive call waits for the result of the next call before completing its multiplication and returning.

Question 14

public class MathUtil {
    // Computes n! for n >= 0
    public static int factorial(int n) {
        // Base case
        if (n == 0) {
            return 1;
        }

        // Recursive step: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
}

1. When n == 1, return 0.
2. When n < 0, return 1.
3. When n == 0, return 1. (correct answer)
4. When n == 0, call factorial(n) again.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying base cases in simple recursive functions. The base case in recursion provides the termination condition and the simplest solution that doesn't require further recursive calls. In this factorial implementation, the base case if (n == 0) return 1 correctly implements the mathematical definition that 0! = 1, which also serves as the stopping point for the recursive calls. Choice C is correct because when n equals 0, the method returns 1, which both matches the mathematical definition of factorial and prevents further recursive calls. Choice D is incorrect because calling factorial(n) again when n == 0 would create infinite recursion, as the parameter wouldn't decrease. To help students: Explain that base cases must move toward termination and provide concrete values. Use the mathematical definition of factorial to justify why 0! = 1, and trace through small examples like 3! to show how recursion eventually reaches the base case.

Question 15

public class MathUtil {
    // Computes n! for n >= 0
    public static int factorial(int n) {
        // Base case
        if (n == 0) {
            return 1;
        }

        // Recursive step
        return n * factorial(n - 1);
    }
}

1. The base case is when n equals 1, returning 1.
2. The base case is when n is negative, returning 0.
3. The base case is when n equals 0, returning 1. (correct answer)
4. The base case is when n equals 4, returning 24.

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying the base case in a recursive factorial implementation. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the factorial method shows a clear base case when n equals 0, returning 1, which correctly implements the mathematical definition that 0! = 1. Choice C is correct because it accurately identifies that the base case occurs when n equals 0, returning 1, which stops the recursion and provides the foundation for building up the factorial calculation. Choice A is incorrect because while 1! = 1, the code doesn't check for n == 1 as a base case; instead, it would recurse to factorial(0) and use the n == 0 base case. To help students: Trace through factorial(4) showing the call stack building up and unwinding. Emphasize that 0! = 1 by definition and explain why this makes a good base case for the recursive formula n! = n × (n-1)!.

Question 16

public static int binarySearch(int[] nums, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (nums[mid] == target) return mid;
    if (target < nums[mid]) return binarySearch(nums, target, low, mid - 1);
    return binarySearch(nums, target, mid + 1, high);
}

1. $O(n)$ because it may check every element
2. $O(\log n)$ because it halves the search interval (correct answer)
3. $O(n \log n)$ because it divides and merges subarrays
4. $O(1)$ because recursion always ends after one call

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on analyzing the time complexity of recursive binary search. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, binary search eliminates half of the remaining search space with each recursive call by comparing the target with the middle element and recursing on only one half. Choice B is correct because the algorithm halves the search interval with each recursive call, resulting in at most log₂(n) recursive calls before finding the target or determining it's not present, giving O(log n) time complexity. Choice A is incorrect because it describes linear search complexity; binary search's key advantage is avoiding the need to check every element by exploiting the sorted order. To help students: Demonstrate how the search space reduces: n → n/2 → n/4 → ... → 1, which takes log₂(n) steps. Compare with linear search to highlight the efficiency gain from using the sorted property.

Question 17

public static int binarySearch(int[] nums, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (nums[mid] == target) return mid;
    if (target < nums[mid]) return binarySearch(nums, target, low, mid - 1);
    return binarySearch(nums, target, mid + 1, high);
}

1. It sorts the entire array before each recursive call
2. It searches both halves every time to guarantee a hit
3. It narrows to one half by updating low or high bounds (correct answer)
4. It removes the middle element from the array each call

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding how binary search narrows its search space. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, binary search compares the target with the middle element and then recursively searches only the appropriate half by adjusting the low or high bounds. Choice C is correct because the algorithm narrows the search to one half of the current range by updating either the high bound to mid-1 (when target < nums[mid]) or the low bound to mid+1 (when target > nums[mid]). Choice B is incorrect because binary search's efficiency comes from eliminating half the search space each time, not searching both halves. To help students: Use a visual representation of an array with arrows showing how low and high bounds move inward. Trace through a specific example showing how the search range shrinks with each recursive call.

Question 18

public static void mergeSort(int[] nums, int left, int right) {
    // Base case
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

1. When left is greater than right, swap the elements
2. When left equals right, merge the two halves immediately
3. When left is greater than or equal to right, return (correct answer)
4. When mid equals left, stop because the array is sorted

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying the base case in merge sort that stops array splitting. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, merge sort checks if left >= right, which handles both single-element subarrays (left == right) and empty subarrays (left > right) that can occur during recursive splitting. Choice C is correct because when left is greater than or equal to right, the subarray has at most one element and is already sorted, so the function returns without further recursive calls or merging. Choice B is incorrect because when left equals right, there's a single element that doesn't need merging with itself; the base case prevents unnecessary operations on already-sorted single elements. To help students: Trace merge sort on a small array showing how subarrays eventually reach size 1. Emphasize that arrays of size 0 or 1 are inherently sorted and form the foundation for building larger sorted arrays through merging.

Question 19

// Recursive binary search on a sorted int array
public static int binarySearch(int[] nums, int target, int low, int high) {
    // Base case: range is empty
    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

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

    // Recursive step: search one half
    if (target < nums[mid]) {
        return binarySearch(nums, target, low, mid - 1);
    } else {
        return binarySearch(nums, target, mid + 1, high);
    }
}

1. When low equals high, return -1 immediately
2. When low is greater than high, return -1 (correct answer)
3. When mid is less than 0, return mid
4. When target is less than nums[mid], return -1

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on understanding the base case in recursive binary search. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the recursive binary search has two base cases: when low > high (empty range) and when nums[mid] == target (element found). Choice B is correct because it correctly identifies that when low is greater than high, the search range is empty and the function returns -1, preventing further recursive calls. Choice A is incorrect because when low equals high, there's still one element to check, so the recursion should continue. To help students: Emphasize that base cases prevent infinite recursion and handle edge conditions. Practice tracing through binary search with small arrays to see when low > high occurs, particularly after unsuccessful searches.

Question 20

public static void quickSort(int[] nums, int low, int high) {
    if (low >= high) {
        return;
    }
    int pivotIndex = partition(nums, low, high);
    quickSort(nums, low, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, high);
}

1. When pivotIndex equals low, return immediately
2. When low is greater than or equal to high, return (correct answer)
3. When the pivot value is the smallest element, return
4. When partition finishes, return without more recursive calls

Explanation: This question tests AP Computer Science A skills on recursive searching and sorting algorithms, focusing on identifying the base case that prevents infinite recursion in quicksort. Recursion involves functions calling themselves with modified parameters until a base case is reached, effectively breaking down a problem into smaller, manageable parts. In this problem, the quicksort algorithm checks if low >= high at the beginning, which handles both empty subarrays (low > high) and single-element subarrays (low == high). Choice B is correct because when low is greater than or equal to high, the subarray has zero or one element and is already sorted, so the function returns without making further recursive calls. Choice A is incorrect because the pivot index position varies and isn't used as the base case condition; the algorithm needs to handle subarrays regardless of where the pivot ends up. To help students: Trace through quicksort with a small array, showing how subarray bounds change. Emphasize that base cases must handle all terminating conditions, including empty ranges that can occur after partitioning.