4.17 Recursive Searching and Sorting

4.17 Recursive Searching and Sorting

Each coding exercise has its own folder. Open its .java file and press Run to try it.

In previous lessons, we learned about searching and sorting algorithms using iteration (loops) to search or sort arrays and ArrayLists. In this lesson, we will take a look at a recursive binary search algorithm and a recursive merge-sort algorithm. Recursion can be used to traverse String objects, arrays, and ArrayList objects.

Recursive Binary Search

We have already seen two search algorithms using loops, linear search and binary search. Linear search searches for an element in an array or ArrayList by checking each element in order. Binary search is more efficient (faster) because it starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList each pass through the algorithm. Binary search only works on sorted data. It can be written with iteration (using a loop) like below or recursively.

Exercise 1

Open the 01-demo-iterative-binary-search-code folder and run IterativeBinarySearch.java. It is an example, so it has no tests.

Watch the iterative binary search code running in the Java Visualizer.

Let’s write a recursive version of Binary Search. Recursive Binary search starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each recursive call until the desired value is found or all elements have been eliminated.

Note that you can write solutions to many problems using recursion or iteration. Iteration is usually preferred and more efficient, but recursive solutions can be elegant and require less code.

What’s the base case for a recursive version of Binary Search (where we want the recursion to stop)? Remember that in binary search, we always check the middle element first when looking for a target element from a startIndex to an endIndex.

Discuss this with your class, or answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-17-recursive-search-sort.html#baseCaseQ

Given a recursive binary search method with the method signature “boolean binarySearch(int[] array, int startIndex, int endIndex, int target)”, what recursive method call would search the array from index 0 to the middle index?

Discuss this with your class, or answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-17-recursive-search-sort.html#recursiveCallQ

Here is the Java code for a recursive binary search.

Exercise 2

Run the code. Try searching for the value 3 and then the value 2 which is not in the array. What would happen if we removed the second base case checking if end < start? Try it and see.

Open the 02-recursiveBinarySearch folder and edit RecursiveBinarySearch.java. This one is not graded, so check it yourself.

Try the recursive binary search code in this Java visualizer link.

Exercise 3

Here is a version of the recursive binary search that works with an ArrayList. Run the code. Try searching for the value 3 and then the value 2 which is not in the ArrayList. What happens?

Open the 03-RecursiveBinarySearchArrayList folder and run RecursiveBinarySearchArrayList.java. It is an example, so it has no tests.

Merge Sort

In previous lessons, 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. Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.

Merge Sort is actually more efficient (faster) than Selection Sort and Insertion Sort because it divides the problem in half each time like binary search. This is called a divide and conquer algorithm.

Merge sort repeatedly divides an array into smaller subarrays until each subarray is one element and then recursively merges the sorted subarrays back together in sorted order to form the final sorted array. The code shown below uses a second array the same size as the original array for merging the values in order. Then it copies all of 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.

The code for mergeSort below is from the AP CSA course description.

To identify a merge sort look for the following:

• 3 methods, mergeSort, mergeSortHelper, and merge
• mergeSortHelper is recursive

Exercise 4

Open the 04-demo-merge-sort-code folder and run SortTest.java. It is an example, so it has no tests.

You can see this executing using the Java visualizer for merge sort.

You can trace through a merge sort algorithm given an array by using parentheses or curly braces to show how the array is divided into subarrays and then merged. For example, here is how you could write down the trace of mergeSort(arr1) where arr1 = {86, 3, 43, 5} like in the example above.

1. Split 1: { {86, 3} , {43, 5} }
2. Split 2: { { {86},{3}} , { {43},{5}} }
3. Merge 1: { {3, 86} , {5,43} }
4. Merge 2: { 3, 5, 43, 86 }

Check your understanding: Under what condition will a merge sort execute faster? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-17-recursive-search-sort.html#qms_1

Check your understanding: Which sort should be the fastest most of the time? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-17-recursive-search-sort.html#qms_2

Tracing Challenge: Recursive Search and Sort

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.

Trace through mergeSort(array) where array = {5, 2, 20, 22, 17, 15, 8, 10} writing down each split and merge.

Discuss this with your class, or answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-17-recursive-search-sort.html#challenge-mergesort

Trace through recursiveBinarySearch(sortedArray, 0, 8, 22) looking for the target number 22 where sortedArray = {2, 5, 8, 10, 11, 15, 17, 20, 22}. Write down each middle element that is checked and the start and end index for each recursive call. How many elements did the binary search have to check before finding 22? How would this compare to a linear search?

Discuss this with your class, or answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/topic-4-17-recursive-search-sort.html#challenge-recursive-binary-search

Summary

• (AP 4.17.A.1) Recursion can be used to traverse String objects, arrays, and ArrayList objects.
• (AP 4.17.B.1) Data must be in sorted order to use the binary search algorithm. Binary search starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each recursive call until the desired value is found or all elements have been eliminated.
• (AP 4.17.B.2) Binary search is typically more efficient than linear search.
• (AP 4.17.B.3) The binary search algorithm can be written either iteratively or recursively.
• (AP 4.17.C.1) Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.
• (AP 4.17.C.2) Merge sort repeatedly divides an array into smaller subarrays until each subarray is one element and then recursively merges the sorted subarrays back together in sorted order to form the final sorted array.

Summary and Review Exercises

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. For 2D arrays, you can do the 2048 lab in AP Classroom or the PictureLab at the end of this unit. The rest of this unit consists of the reviews for each section of the unit.

• Recursion Summary
• Recursion Parsons Practice
• Recursion Mixed Up Code Practice
• Recursion Code Practice
• Recursion Exercises