LockInCS

Unit 4 · 25 min

4.17 Recursive Searching and Sorting

Binary search and merge sort both win by splitting the problem in half again and again.

Summary, objectives and course and exam description (CED) codes

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.

By the end of this session you can

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

4.17.A4.17.A.14.17.B4.17.B.14.17.B.24.17.B.34.17.C4.17.C.14.17.C.2

Reviewed against the CED on

Know this already? Jump to the checkpoint.

1LearnThe notes, the traps and how to remember them

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.

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.

Lock it in: memory hooks

  • Binary searchGuess the middle page of a dictionary, then throw away the half that cannot hold your word.
  • Binary search preconditionNo sort, no binary search.
  • Merge sortSplit until each piece is trivially sorted, then zip pairs of sorted piles together, smallest card first.

Common misconceptions

  • "Binary search works on any array, it just runs faster on a sorted one."

    Not quite. 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.

  • "Binary search always finds the target faster than linear search."

    Not quite. 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.

  • "Merge sort sorts while it splits the array."

    Not quite. 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.

Exam traps

  • mid = (low + high) / 2 uses integer division: (0 + 7) / 2 is 3, not 3.5.
  • After checking mid, the next range is low to mid - 1 or mid + 1 to high; mid itself is never checked again.
  • Binary search on unsorted data compiles and runs, but can return a wrong result.
  • Merge sort questions ask for the subarrays after a given merge: trace the left half completely before the right half.
  • The only searches in scope are linear and binary search; the only sorts are selection, insertion and merge sort.

2PracticeRecall it, then check yourself

In 30 seconds

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

Cover this list, say the points out loud, then take the checkpoint without scrolling back up.

Checkpoint · 6 questions

Checkpoint: Recursive Searching and Sorting

Pick an answer to mark it. Every answer is explained, and you can try any question again. Your saved score counts first tries only, and stays in this browser.

  1. 1 Consider the following method. What value is returned by the call drop("banana")? 4.17.A.1 
    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;
}
    Show answer

    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.

  2. 2 Consider the following method. What value is returned by the call addSome(new int[] {4, 9, 2, 7, 6}, 0)? 4.17.A.1 
    public static int addSome(int[] arr, int i)
{
    if (i >= arr.length)
    {
        return 0;
    }
    return arr[i] + addSome(arr, i + 2);
}
    Show answer

    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.

  3. 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)? 4.17.B.1, 4.17.B.3 
    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;
}
    Show answer

    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.

  4. 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)? 4.17.B.1
    Show answer

    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.

  5. 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? 4.17.B.2
    Show answer

    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.

  6. 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? 4.17.C.1, 4.17.C.2
    Show answer

    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.

3PrevailLock it in for exam day

By the numbers

Name each list from memory, then reveal it to check. Each list shows how many items to recall.

Key terms: flip the cards

Read the term, say the definition out loud, then flip to check. Struggling a little to remember is what makes it stick.

  • Binary searchtap to flip

    A search algorithm for sorted data that checks the middle element and eliminates half of the remaining elements each step.

    Example and CED codes
  • Merge sorttap to flip

    A recursive sort that divides an array into one-element subarrays, then merges sorted subarrays back together in order.

    Example and CED codes
  • Linear searchtap to flip

    A search algorithm that checks each element in order until it finds the desired value or has checked every element.

    Example and CED codes
  • Recursiontap to flip

    A form of repetition in which a method calls itself; it needs at least one base case and at least one recursive call.

    Example and CED codes
  • Base casetap to flip

    The condition in a recursive method where it returns without calling itself again, which halts the recursion.

    Example and CED codes
  • Recursive calltap to flip

    A call in which a method calls itself, usually with parameter values that move closer to the base case.

    Example and CED codes

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.

Was this page helpful?

No names are ever shown, and every public comment is checked by us first. Please do not include personal details. To get a reply, email [email protected].

↑ Top

Enlarged view of the selected figure