Aim for FiveComputer Science A

Unit 4 · Topic 4.17

4.17 Recursive Searching and Sorting

Recursion can walk through strings, arrays and lists, and two important algorithms use it: binary search, which finds a value in sorted data by cutting the search area in half each step, and merge sort, which sorts by splitting a list in half, sorting each half and merging. You need to trace each step of both.

Key terms

  • binary search
  • sorted data
  • merge sort
  • divide and conquer
  • merge

Recursive traversals

A recursive method can traverse a string, array or ArrayList by handling one position and then calling itself for the rest. An index parameter tracks the progress, and the base case is reaching the end:

public static int countFrom(String s, int i) { if (i >= s.length()) { return 0; } int rest = countFrom(s, i + 1); if (s.substring(i, i + 1).equals("s")) { return rest + 1; } return rest; }

countFrom("mississippi", 0) counts all four s's. Starting at index 5, it only looks at "ssippi", so it returns 2.

Binary search

Binary search only works on sorted data. It looks at the middle element. If that's the target, it's done. If the target is bigger, it can't be in the left half, so it throws that half away and searches the right half; if smaller, it searches the left half. Each step eliminates half of what's left, until it finds the target or nothing is left.

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

low and high mark the part still being searched, and mid uses integer division, so it rounds down. When low passes high, the range is empty and the method returns -1.

Binary search can be written with recursion, as here, or with a while (low <= high) loop. Both versions check the same elements in the same order.

Why binary search is faster

Halving shrinks the search area very quickly. A sorted list of 1,000 elements takes at most 10 checks, while linear search might need 1,000. That's why binary search is usually much more efficient. The catch is that the data has to be sorted first; on unsorted data, binary search can miss a value that's there.

Merge sort

Merge sort is a recursive sort that uses divide and conquer:

  • Split the list into two halves.
  • Merge sort each half (the recursive calls). A part with one element is already sorted, which is the base case.
  • Merge the two sorted halves into one sorted list: repeatedly compare the front elements of the two halves and take the smaller one, until both halves are used up.

The merge sort code

public static void mergeSort(int[] arr, int low, int high) { if (low < high) { int mid = (low + high) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } }

The merge helper does the third step using a temporary array. All of the actual sorting happens during the merges; the splitting just breaks the list into pieces small enough to be sorted already.

Not on the exam

Linear and binary search are the only searches in the course, and selection, insertion and merge sort are the only sorts.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Tracing binary search

    This version prints low, high, mid and arr[mid] at each step. What does the code print when it searches {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} for 23 and then for 10?public static int bs(int[] arr, int target, int low, int high) { if (low > high) { System.out.println("low " + low + " > high " + high); return -1; } int mid = (low + high) / 2; System.out.println(low + " " + high + " " + mid + " " + arr[mid]); if (arr[mid] == target) { return mid; } if (arr[mid] < target) { return bs(arr, target, mid + 1, high); } return bs(arr, target, low, mid - 1); }

    Show the solution
    1. Step 1: Searching for 23. Step 1: low 0, high 9, mid (0 + 9) / 2 = 4, and arr[4] is 16. 16 < 23, so search the right half: low becomes 5.
    2. Step 2: Step 2: low 5, high 9, mid 7, arr[7] is 56. 56 > 23, so search the left part: high becomes 6.
    3. Step 3: Step 3: low 5, high 6, mid 5, arr[5] is 23. Found: return 5. Only 3 elements were checked.
    4. Step 4: Searching for 10: mid 4 (16 > 10, so high = 3), then mid 1 (5 < 10, so low = 2), then mid 2 (8 < 10, so low = 3), then mid 3 (12 > 10, so high = 2).
    5. Step 5: Now low (3) is greater than high (2), so the range is empty and it returns -1. It checked 16, 5, 8 and 12.

    Answer: For 23 it prints 0 9 4 16, 5 9 7 56, 5 6 5 23 and then 5. For 10 it prints 0 9 4 16, 0 3 1 5, 2 3 2 8, 3 3 3 12, low 3 > high 2 and then -1.

  2. Example 2

    Tracing merge sort

    Merge sort is called on {6, 3, 8, 1, 7, 2, 5, 4} using the code above. List the merges in the order they happen.

    Show the solution
    1. Step 1: The first call splits the list into {6, 3, 8, 1} and {7, 2, 5, 4}, and fully sorts the left half before touching the right half.
    2. Step 2: The left half splits into {6, 3} and {8, 1}. {6, 3} splits into single elements, which merge into {3, 6}. Then {8, 1} becomes {1, 8}.
    3. Step 3: Merging {3, 6} and {1, 8}: compare the fronts, 3 and 1, take 1; then 3 and 8, take 3; then 6 and 8, take 6; then 8 is left. Result: {1, 3, 6, 8}.
    4. Step 4: The right half does the same: {7, 2} becomes {2, 7}, {5, 4} becomes {4, 5}, and those merge into {2, 4, 5, 7}.
    5. Step 5: The final merge of {1, 3, 6, 8} and {2, 4, 5, 7} gives {1, 2, 3, 4, 5, 6, 7, 8}. That's seven merges in all, and the left half finishes all of its merges before the right half starts.

    Answer: The merges, in order: {3, 6}, {1, 8}, {1, 3, 6, 8}, {2, 7}, {4, 5}, {2, 4, 5, 7}, {1, 2, 3, 4, 5, 6, 7, 8}.

Common mistakes

  • Using binary search on unsorted data. It only works when the data is sorted.
  • Rounding mid up. With int division, (low + high) / 2 always rounds down.
  • Thinking merge sort sorts as it splits. The splitting only breaks the list apart; the sorting happens in the merges.
  • Tracing merge sort's two halves at the same time. The left half is completely sorted before the right half starts.

On the exam

  • Expect questions that ask which elements binary search checks, how many steps it takes, or what the list looks like after a certain merge. Write low, high and mid for every step.

Connected topics

Videos

Check yourself

5 questions on 4.17 Recursive Searching and Sorting. Pick an answer to see if you got it, and why.

Question 1 of 5

Consider the following method.public static String rev(String s) { if (s.length() <= 1) { return s; } return rev(s.substring(1)) + s.substring(0, 1); }What value is returned by the call rev("step")?

Question 2 of 5

Consider the following method.public static int sumFrom(int[] arr, int i) { if (i >= arr.length) { return 0; } return arr[i] + sumFrom(arr, i + 2); }Assume vals is {4, 1, 6, 3, 5}. What value is returned by sumFrom(vals, 0)?

Code
public static int binarySearch(int[] arr, int target, int low, int high)
{
    if (low > high)
    {
        return -1;
    }
    int mid = (low + high) / 2;
    if (arr[mid] == target)
    {
        return mid;
    }
    else if (arr[mid] < target)
    {
        return binarySearch(arr, target, mid + 1, high);
    }
    else
    {
        return binarySearch(arr, target, low, mid - 1);
    }
}
Question 3 of 5

Assume data is declared as follows.int[] data = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};The call binarySearch(data, 23, 0, data.length - 1) is made. Which of the following lists the elements of data that are compared with 23, in order?

Question 4 of 5

Why must the array be sorted before binarySearch is used?

Question 5 of 5

For a sorted array of 1,000 different values, what is the greatest number of elements binarySearch ever compares with the target, whether or not it is found?

0 of 5 answered