R.2: RECURSIVE SEARCHING AND SORTING

OBJECTIVES

I can:

• apply recursive search algorithms to information in String, 1D array, or ArrayList objects

• apply recursive algorithms to sort elements of an array or ArrayList objects

In the ArrayList unit 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 recursive binary search and recursive merge-sort algorithms.

RECURSIVE BINARY SEARCH

Remember, 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 and can be written with iteration (using a loop) like below OR recursively.

Let's take a look at a recursive version of Binary Search.

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.

Here is the Java code for a recursive binary search:

MERGE SORT

In the ArrayList unit we also 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 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.

A merge sort recursively breaks the values to be sorted in half until there is only one value to be sorted and then it breges the two sorted lists into one sorted list.

The code shown below uses a second array the same size as the original array for merging the values in order.

Then if copies all of the sorted values back into the original array.

Check out this folk dance video which shows the merge sort process:

And here is a short video which describes how merge sort works:

To identify a merge sort look for the following:

• Three methods (mergeSort, mergeSortHelper, and merge)

• mergeSortHelper is recursive

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 }

SUMAMRY

• The binary search algorithm can be written either iteratively or recursively.

• Data must be in sorted order to used the binary  search algorithm.

• The binary search algorithm starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in until the desired value is found or all elements have been eliminated.

• Binary search can be more efficient than sequential/linear search.

• Merge sort is a recursive sorting algorithm that can be used to sort elements in an array  or ArrayList.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

R.2 Evidence

2) Create Your Own Assignment! Remember, the OBJECTIVES of this lesson are to be able to apply recursive search algorithms to information in String, 1D array, or ArrayList objects AND to apply recursive algorithms to sort elements of an array or ArrayList objects. What EVIDENCE can you present to prove that you can do these things? Meet with Mr. C when you are ready to present. In other words, show me what you can do!

3) MC Exam Practice: This lesson has additional practice problems which can be found on the MC Exam Practice page with an answer key! Use ctrl + f to search for different objectives throughout the year. You could look at these questions now, or, save these practice questions for later and use them to review! The choice is yours.