BHSawesome AP CSA

In Subsection 12.1.3 Binary search we saw how to implement a binary search using a loop. And in the previous lesson we learned that recursion, while it can be used for linear traversals, is most powerful as “loops for trees”. Let’s look at another way of thinking about binary search that lends itself naturally to a recursive solution.

For reference, here’s the iterative binary search from Subsection 12.1.3 Binary search.

public class BinarySearch {

    public static int search(int[] nums, int n) {

        int low = 0;
        int high = nums.length;

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] < n) {
                low = mid + 1;
            } else if (nums[mid] > n) {
                high = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

Now let’s consider how that algorithm proceeds. Let’s assume we’re searching an array with length 8. So the low and high variables will start at 0 and 8, representing the half-open interval \([0, 8)\text{.}\) And the first value of mid will be 4. On the next iteration of the loop low and high will be either 0 and 4 or 4 and 8, depending on which half of the original range the target value is determined to be in. And then whichever range we end up in, on the next iteration it will be split in half one one of it’s halves chosen and so on until we get down to ranges containing just a single number.

While in any given call to search we will go down one path until we find, or fail to find, our target number. But we could also think of the possible paths as a tree that starts with one range covering the whole range and then has children that represent each half, and each of them have children representing their two halves until we reach the leaves containing only one number each. We can draw the tree like this.

With that tree in mind, we can write a recursive version of binary search. Unlike our iterative binary search method, the recursive search needs to take two extra arguments that specify what part of the array any single call is responsible for. The first call will pass a range covering the whole array and then each recursive calls will narrow the range to one half of the range. In other words, to find a number in a given range we determine which half of that range it’s in and then find in in that smaller range. Eventually the range will get small enough that we either found it or we know it’s not there.

Before we look at the code, try to answer these questions.

Try the recursive binary search code in this visualization or with the CodeLens button above.

Note that binary search is one of many algorithms that can be written either using loops or recursively. Which you prefer when is largely a matter of taste though all other things being equal, in many languages iteration is preferred and likely to be more efficient. On the other hand, for some algorithms, it can be very straightforward to express them recursively and very difficult to translate them into iterative code.

In Section 12.2 Sorting algorithms, we looked at two sorting algorithms, selection sort and insertion sort. In this lesson, we will look at a third sorting algorithm, merge sort, which uses recursion. In this case recursion makes the algorithm more efficient than either of the other two algorithms we’ve looked it.

Similar to how the recursive binary search worked by searching smaller and smaller sub-ranges of the original array, merge sort repeatedly divides ranges covering part of the array into smaller sub-ranges until each range is just one element wide and then recursively merges adjacent ranges back together in sorted order.

For example, after four adjacent one-element ranges are merged into two adjacent two-element ranges, those two-element ranges are merged into one four-element range, and so on until on the very last step, the sorted first half of the array is merged with the sorted second half of the array, completing the sort.

Merge sort typically uses a second array the same size as the original array to hold the values while merging and then copies the sorted values back into the original array.

Here is a folk dance video that shows the merge sort process.

And here is a short video that describes how merge sort works.

And here is an implementation of merge sort. Note that the only public method here is sort but it is written in terms of two helper methods: sortRange and merge. The sortRange method is actually the recursive method. Since recursive methods often need some extra arguments to specify what sub-problem each recursive call is working on, it’s common to write a non-recursive method that calls a recursive method with the right initial arguments to kick things off. Here sort calls sortRange with the range covering the whole array.

You can see this executing using this visualization or the CodeLens button above.

To understand merge sort it can be useful to trace through the steps using parentheses or curly braces to show how the array is divided into sub-arrays and then merged. For example, here is a trace of of sorting the array {86, 3, 43, 5} from the code above.

Working in pairs, practice the recursive binary search and merge sort algorithms with a deck of cards or pieces of paper with numbers or names on them. Here’s a video that shows merge sort with cards.

Work in pairs to do the following tracing problems.

This lesson is the last lesson in Unit 4! Congratulations! Now, it’s time to practice before the exam.

You can now do the following review lessons about recursion at the end of the unit and College Board Progress Check for Unit 4 Part 3 in the AP Classroom. The rest of this unit consists of the reviews for each section of the unit.