# AP® Computer Science A 4.17 Recursive Searching and Sorting

Source: https://lockincs.com/ap-csa/unit-4/4-17-recursive-searching-and-sorting/  
Last reviewed against the College Board Course and Exam Description (CED): 2026-11-12  
CED codes: 4.17.A, 4.17.A.1, 4.17.B, 4.17.B.1, 4.17.B.2, 4.17.B.3, 4.17.C, 4.17.C.1, 4.17.C.2

Recursion can traverse String objects, arrays and ArrayList objects. Binary search needs sorted data: it starts at the middle and eliminates half of the remaining elements each time, so it is typically more efficient than linear search, and it can be written iteratively or recursively. Merge sort is a recursive sort that divides an array into one-element subarrays, then merges sorted subarrays back together.

## What you will learn

- 4.17.A Determine the result of executing recursive algorithms that use strings or collections.
- 4.17.B Determine the result of each iteration of a binary search algorithm used to search for information in a collection.
- 4.17.C Determine the result of each iteration of the merge sort algorithm when used to sort a collection.

## 1\. Recursion over strings and collections

Recursion can traverse String objects, arrays and ArrayList objects 4.17.A.1. The parameter that changes is either an index that moves through the collection or a shorter version of the String. The base case is “nothing left to visit”.

```
public static int countVowels(String s)
{
    if (s.length() == 0)
    {
        return 0;
    }
    int first = 0;
    if ("aeiou".indexOf(s.substring(0, 1)) >= 0)
    {
        first = 1;
    }
    return first + countVowels(s.substring(1));
}

public static int maxFrom(int[] arr, int index)
{
    if (index == arr.length - 1)
    {
        return arr[index];
    }
    int restMax = maxFrom(arr, index + 1);
    if (arr[index] > restMax)
    {
        return arr[index];
    }
    return restMax;
}

public static String joinBackward(ArrayList<String> list, int index)
{
    if (index < 0)
    {
        return "";
    }
    return list.get(index) + " " + joinBackward(list, index - 1);
}

System.out.println(countVowels("banana"));
int[] heights = {152, 171, 166, 160};
System.out.println(maxFrom(heights, 0));
ArrayList<String> route = new ArrayList<String>();
route.add("home");
route.add("park");
route.add("school");
System.out.println(joinBackward(route, route.size() - 1));
```

Output:

```
3
171
school park home 
```

Trace of `maxFrom(heights, 0)`: the calls go down with index 0, 1, 2, 3. The base case returns 160; index 2 compares 166 with 160 and returns 166; index 1 compares 171 with 166 and returns 171; index 0 compares 152 with 171 and returns 171.

## 2\. Binary search: the idea and the precondition

Binary search only works on data in **sorted order** 4.17.B.1. It starts at the middle element of a sorted array or ArrayList. If the middle element is the target, it is done. If not, the target can only be in one half, so binary search eliminates the other half and repeats on what is left, until the desired value is found or all elements have been eliminated 4.17.B.1.

The algorithm keeps two indexes, `low` and `high`, around the part that is still possible, and checks `mid = (low + high) / 2` (integer division). Binary search can be written either iteratively or recursively 4.17.B.3. Here is the iterative version, printing each step:

```
public static int binarySearch(int[] arr, int target)
{
    int low = 0;
    int high = arr.length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        System.out.println("low " + low + ", high " + high + ", mid " + mid + ", arr[mid] " + arr[mid]);
        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;     // eliminate the left half
        }
        else
        {
            high = mid - 1;    // eliminate the right half
        }
    }
    return -1;
}

int[] ids = {3, 8, 14, 21, 27, 35, 42, 50, 61};
System.out.println("found at " + binarySearch(ids, 42));
System.out.println("found at " + binarySearch(ids, 10));
```

Output:

```
low 0, high 8, mid 4, arr[mid] 27
low 5, high 8, mid 6, arr[mid] 42
found at 6
low 0, high 8, mid 4, arr[mid] 27
low 0, high 3, mid 1, arr[mid] 8
low 2, high 3, mid 2, arr[mid] 14
found at -1
```

Trace of the search for 10:

| Search for 10 | low | high | mid | arr\[mid\] | Decision |
| --- | --- | --- | --- | --- | --- |
| step 1 | 0 | 8 | 4 | 27 | 10 < 27: high = 3 |
| step 2 | 0 | 3 | 1 | 8 | 10 > 8: low = 2 |
| step 3 | 2 | 3 | 2 | 14 | 10 < 14: high = 1 |
| end | 2 | 1 |  |  | low > high: return -1 |

Watch out: on unsorted data the code still compiles and runs, but it can discard the half that holds the target and return -1 for a value that is in the array.

## 3\. Recursive binary search

The recursive version passes `low` and `high` as parameters 4.17.B.3. Each recursive call eliminates half of the remaining elements 4.17.B.1. There are two base cases: the target is found, or `low > high` (nothing left).

```
public static int search(int[] arr, int target, int low, int high)
{
    if (low > high)
    {
        return -1;                                   // base case: nothing left
    }
    int mid = (low + high) / 2;
    System.out.println("search(" + low + ", " + high + ") checks index " + mid);
    if (arr[mid] == target)
    {
        return mid;                                  // base case: found
    }
    if (arr[mid] < target)
    {
        return search(arr, target, mid + 1, high);   // right half
    }
    return search(arr, target, low, mid - 1);        // left half
}

int[] ids = {3, 8, 14, 21, 27, 35, 42, 50, 61};
System.out.println("result " + search(ids, 61, 0, ids.length - 1));
```

Output:

```
search(0, 8) checks index 4
search(5, 8) checks index 6
search(7, 8) checks index 7
search(8, 8) checks index 8
result 8
```

The recursive version checks exactly the same middle elements as the iterative version would. The parameters `low` and `high` capture the progress, just like the two variables in the loop.

## 4\. Why binary search is typically more efficient

Binary search is typically more efficient than linear search 4.17.B.2. Each check halves what is left, so the number of checks grows very slowly as the data grows.

```
public static int linearChecks(int[] arr, int target)
{
    int checks = 0;
    for (int i = 0; i < arr.length; i++)
    {
        checks++;
        if (arr[i] == target)
        {
            return checks;
        }
    }
    return checks;
}

public static int binaryChecks(int[] arr, int target)
{
    int checks = 0;
    int low = 0;
    int high = arr.length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        checks++;
        if (arr[mid] == target)
        {
            return checks;
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return checks;
}

int[] sizes = {8, 1000, 1000000};
for (int n : sizes)
{
    int[] data = new int[n];
    for (int i = 0; i < n; i++)
    {
        data[i] = i * 2;          // sorted even numbers
    }
    System.out.println(n + " elements, target absent: linear " + linearChecks(data, -1)
        + ", binary " + binaryChecks(data, -1));
}
int[] small = {2, 4, 6, 8, 10, 12, 14, 16};
System.out.println("target first: linear " + linearChecks(small, 2) + ", binary " + binaryChecks(small, 2));
```

Output:

```
8 elements, target absent: linear 8, binary 3
1000 elements, target absent: linear 1000, binary 9
1000000 elements, target absent: linear 1000000, binary 19
target first: linear 1, binary 3
```

| Elements n | Linear search, worst case | Binary search, worst case |
| --- | --- | --- |
| 8 | 8 checks | 4 checks |
| 1,000 | 1,000 checks | 10 checks |
| 1,000,000 | 1,000,000 checks | 20 checks |

The worst case for binary search is about log2(n) + 1 checks (the run above used a target smaller than every element, which takes one check less than the worst case). The last line shows why binary search is only “typically” more efficient: when the target is the first element, linear search wins. Scope note: linear search and binary search are the only search algorithms on the AP® exam 4.17.B.2.

## 5\. Merge sort

Merge sort is a recursive sorting algorithm for an array or ArrayList 4.17.C.1. It repeatedly divides the array into smaller subarrays until each subarray has one element, which is already sorted. Then it recursively merges the sorted subarrays back together, in sorted order, to form the final sorted array 4.17.C.2.

To **merge** two sorted subarrays, compare their front elements, copy the smaller one into a temporary array, and repeat; when one side runs out, copy the rest of the other side.

```
public static void mergeSort(int[] arr)
{
    int[] temp = new int[arr.length];
    sortRange(arr, temp, 0, arr.length - 1);
}

public static void sortRange(int[] arr, int[] temp, int from, int to)
{
    if (from >= to)
    {
        return;                                  // one element: already sorted
    }
    int middle = (from + to) / 2;
    sortRange(arr, temp, from, middle);          // sort the left half
    sortRange(arr, temp, middle + 1, to);        // sort the right half
    merge(arr, temp, from, middle, to);          // merge the two sorted halves
}

public static void merge(int[] arr, int[] temp, int from, int middle, int to)
{
    int i = from;
    int j = middle + 1;
    int k = from;
    while (i <= middle && j <= to)
    {
        if (arr[i] <= arr[j])
        {
            temp[k] = arr[i];
            i++;
        }
        else
        {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    while (i <= middle)
    {
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= to)
    {
        temp[k] = arr[j];
        j++;
        k++;
    }
    String merged = "";
    for (k = from; k <= to; k++)
    {
        arr[k] = temp[k];
        merged += arr[k] + " ";
    }
    System.out.println("merge " + from + " to " + to + ": " + merged);
}

int[] scores = {38, 16, 27, 5, 49, 12, 30, 21};
mergeSort(scores);
```

Output:

```
merge 0 to 1: 16 38 
merge 2 to 3: 5 27 
merge 0 to 3: 5 16 27 38 
merge 4 to 5: 12 49 
merge 6 to 7: 21 30 
merge 4 to 7: 12 21 30 49 
merge 0 to 7: 5 12 16 21 27 30 38 49 
```

Divide, then merge. Read the divide phase top to bottom and the merge phase in the order the merges happen:

| Phase | Subarrays |
| --- | --- |
| start | \[38 16 27 5 49 12 30 21\] |
| divide | \[38 16 27 5\] \[49 12 30 21\] |
| divide | \[38 16\] \[27 5\] \[49 12\] \[30 21\] |
| divide (one element each) | \[38\] \[16\] \[27\] \[5\] \[49\] \[12\] \[30\] \[21\] |
| merge 1 | \[16 38\] \[27\] \[5\] \[49\] \[12\] \[30\] \[21\] |
| merge 2 | \[16 38\] \[5 27\] \[49\] \[12\] \[30\] \[21\] |
| merge 3 | \[5 16 27 38\] \[49\] \[12\] \[30\] \[21\] |
| merge 4 | \[5 16 27 38\] \[12 49\] \[30\] \[21\] |
| merge 5 | \[5 16 27 38\] \[12 49\] \[21 30\] |
| merge 6 | \[5 16 27 38\] \[12 21 30 49\] |
| merge 7 | \[5 12 16 21 27 30 38 49\] |

Watch out: because the left half is sorted completely before the right half starts, the whole left half \[5 16 27 38\] is finished (merge 3) before 49 and 12 are merged (merge 4).

Merging \[5 16 27 38\] with \[12 21 30 49\] (the last merge) step by step:

| Compare | Smaller goes to temp | temp so far |
| --- | --- | --- |
| 5 vs 12 | 5 | 5 |
| 16 vs 12 | 12 | 5 12 |
| 16 vs 21 | 16 | 5 12 16 |
| 27 vs 21 | 21 | 5 12 16 21 |
| 27 vs 30 | 27 | 5 12 16 21 27 |
| 38 vs 30 | 30 | 5 12 16 21 27 30 |
| 38 vs 49 | 38 | 5 12 16 21 27 30 38 |
| left side empty | copy 49 | 5 12 16 21 27 30 38 49 |

Informally, merge sort does about n times log2(n) steps (log2(n) levels of merging, about n steps per level). For 8 elements that is about 24 steps, and for 1,000 elements about 10,000, compared with 499,500 comparisons for selection sort. Scope note: selection sort, insertion sort and merge sort are the only sorting algorithms on the AP® exam 4.17.C.1.

## Common mix-ups

- Not true: Binary search works on any array, it just runs faster on a sorted one. Binary search requires sorted data. On unsorted data it can throw away the half that holds the target and report -1 even though the value is there.
- Not true: Binary search always finds the target faster than linear search. It is typically more efficient, especially on large data. But if the target is the first element, linear search finds it in one comparison while binary search starts in the middle.
- Not true: Merge sort sorts while it splits the array. Splitting only divides the array into smaller subarrays until each has one element. All the ordering happens in the merge steps, on the way back up.

## In 30 seconds

- A recursive method can traverse a String, array or ArrayList by moving an index (or a shorter substring) toward a base case.
- Binary search needs sorted data, checks the middle element and eliminates half of the remaining elements each step.
- Binary search can be written with a loop or with recursion; both check the same middle elements.
- For n elements binary search needs about log2(n) + 1 checks in the worst case; linear search needs n.
- Merge sort divides until each subarray has one element, then merges sorted subarrays into larger sorted subarrays.

## Checkpoint: 6 practice questions

### Question 1

Consider the following method. What value is returned by the call `drop("banana")`?

```java
public static String drop(String s)
{
    if (s.length() == 0)
    {
        return "";
    }
    String first = s.substring(0, 1);
    if (first.equals("a"))
    {
        return drop(s.substring(1));
    }
    return drop(s.substring(1)) + first;
}
```

- A. bnn
- B. nnb
- C. aaa
- D. ananab

**Answer: B.** Each call skips the first letter if it is "a" and otherwise adds it after the result of the recursive call, so the kept letters come out in reverse order. The kept letters of "banana" are b, n, n; reversed, they give "nnb". "bnn" would need the first letter in front of the recursive result, "aaa" keeps the wrong letters, and "ananab" reverses without dropping anything.

### Question 2

Consider the following method. What value is returned by the call `addSome(new int[] {4, 9, 2, 7, 6}, 0)`?

```java
public static int addSome(int[] arr, int i)
{
    if (i >= arr.length)
    {
        return 0;
    }
    return arr[i] + addSome(arr, i + 2);
}
```

- A. 28
- B. 16
- C. 12
- D. 6

**Answer: C.** The index starts at 0 and goes up by 2 each call: 0, 2, 4, then 6, which is the base case. The method adds the elements at even indexes, 4 + 2 + 6 = 12. 28 adds every element, 16 adds the odd indexes, and 6 stops before index 4.

### Question 3

Consider the following method, which prints each value it examines. What is printed as a result of the call `binarySearch(new int[] {2, 5, 9, 12, 17, 23, 30, 41}, 30)`?

```java
public static int binarySearch(int[] arr, int target)
{
    int low = 0;
    int high = arr.length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        System.out.print(arr[mid] + " ");
        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}
```

- A. 12 23 30
- B. 17 30
- C. 12 30
- D. 2 5 9 12 17 23 30

**Answer: A.** First low is 0 and high is 7, so mid is 3 and 12 is examined; 30 is larger, so low becomes 4. Then mid is 5 (23), so low becomes 6. Then mid is 6 and 30 is found. 17 30 rounds the middle up, 12 30 skips a step, and 2 5 9 12 17 23 30 is a linear search.

### Question 4

The `binarySearch` method from the previous question, with its print statement removed, is called on an array that is NOT sorted. What value is returned by the call `binarySearch(new int[] {8, 3, 15, 1, 20, 11, 6}, 3)`?

- A. 1
- B. -1
- C. 3
- D. 0

**Answer: B.** Binary search requires sorted data. It examines 1 (index 3), and since 3 is larger it eliminates the left half, which is where 3 actually is. It then examines 11 and 20 and runs out of elements, returning -1. 1 is the real index of 3, which only a linear search would find; 3 and 0 are other indexes it never returns.

### Question 5

A sorted array holds 1,000 different integers, and the value being searched for is not in the array. Which of the following best describes the number of elements examined in the worst case by binary search and by linear search?

- A. Binary search: 500; linear search: 1,000
- B. Binary search: 1,000; linear search: 10
- C. Binary search: 100; linear search: 1,000
- D. Binary search: 10; linear search: 1,000

**Answer: D.** Binary search halves the remaining elements with each check, so at most 10 checks are needed (after 10 halvings, 1,000 elements are all eliminated, since 2 to the 10th power is 1,024). Linear search must check all 1,000 elements before it can report that the value is absent. 500 and 100 assume binary search removes far fewer elements each step, and the second option swaps the two algorithms.

### Question 6

Merge sort is used to sort the array `{9, 4, 7, 2, 8, 1}` into increasing order. The array is divided into the halves `{9, 4, 7}` and `{2, 8, 1}`. Which of the following shows the two subarrays immediately before the final merge?

- A. `{4, 9, 7}` and `{2, 8, 1}`
- B. `{1, 2, 4}` and `{7, 8, 9}`
- C. `{4, 7, 9}` and `{1, 2, 8}`
- D. `{2, 4, 9}` and `{1, 7, 8}`

**Answer: C.** Merge sort recursively sorts each half completely before the final merge combines them, so the left half becomes {4, 7, 9} and the right half becomes {1, 2, 8}. {4, 9, 7} and {2, 8, 1} are only partly sorted, {1, 2, 4} and {7, 8, 9} assume the values were exchanged between halves before merging, and the last option mixes values from both halves.

## Questions students ask

**Why must the data be sorted for binary search?**

Binary search decides which half to throw away by comparing the target with the middle element. That decision is only correct when every element to the left is smaller and every element to the right is larger.

**How many comparisons does binary search make?**

Each check halves the remaining elements, so for n elements the worst case is about log2(n) + 1 checks: for example 4 checks for 8 elements and 10 checks for 1,000 elements, compared with up to 1,000 for linear search.

**How does merge sort work step by step?**

Merge sort splits the array in half, sorts each half with the same method (recursively) until a subarray has one element, and then merges the two sorted halves by repeatedly taking the smaller front element.

**Is merge sort faster than selection sort and insertion sort?**

For large data, usually yes. Merge sort does about n times log2(n) steps, while selection sort always makes n(n - 1) / 2 comparisons. For small or nearly sorted data, insertion sort can be just as fast.

**Can binary search be written without recursion?**

Yes. Binary search can be written iteratively with a while loop that updates low and high, or recursively with low and high as parameters. Both check the same sequence of middle elements.

---

© LockInCS, licensed CC BY-NC-ND 4.0. AP® is a trademark registered by the College Board, which is not affiliated with, and does not endorse, this website.