Introduction to Recursive Searching and Sorting

In our previous chapters, we looked at how to search for items and sort lists using loops (iteration). However, some of the most powerful algorithms in computer science use a "Divide and Conquer" strategy. Instead of looking at a whole list at once, these algorithms break the problem into smaller and smaller pieces until they are easy to solve. In this chapter, we will focus on Recursive Binary Search and Merge Sort.

Note: For the AP Exam, you do not need to write recursive code from scratch. You only need to be able to trace and analyze provided recursive code to determine what it does or what it outputs.

Binary Search is a highly efficient way to find an item in a sorted collection. It works by looking at the middle element and "eliminating half" of the remaining elements in each step.

How the Recursion Works

To perform a binary search recursively, the method calls itself with a new range (new start or end indices). Here is the logic:

  1. Base Case 1: If the starting index is greater than the ending index, the item is not in the list. Return \( -1 \).
  2. Find the Midpoint: Calculate \( mid = (low + high) / 2 \).
  3. Base Case 2: If the element at \( mid \) is the target, return \( mid \).
  4. Recursive Step (Left): If the target is smaller than the element at \( mid \), call the search again on the left half (from \( low \) to \( mid - 1 \)).
  5. Recursive Step (Right): If the target is larger than the element at \( mid \), call the search again on the right half (from \( mid + 1 \) to \( high \)).

Analogy: Imagine looking for a word in a physical dictionary. You open it to the middle. If the word you want comes before the current page, you ignore the entire second half of the book and repeat the process with the first half. You keep "halving" the book until you find your word.

Quick Review: Binary Search Requirements

  • The data must be sorted. If the array is unsorted, Binary Search will not work!
  • It is much faster than Linear Search for large data sets because it cuts the work in half every time.

2. Merge Sort

Merge Sort is the primary recursive sorting algorithm you need to know for the AP CSA exam. It also follows the "Divide and Conquer" philosophy.

The Two Phases of Merge Sort

Merge Sort works in two distinct phases: Splitting and Merging.

Phase 1: The Recursive Split
The algorithm takes an array and recursively divides it into two halves until it reaches the Base Case: an array with only one element. (An array with one element is, by definition, already sorted!)

Phase 2: The Merge
Once the arrays are split into single elements, the algorithm begins merging them back together in the correct order. It compares the smallest items of two subarrays and places them into a temporary array in sorted order.

Informal Run-Time Analysis

In the AP curriculum, we compare algorithms by counting statement executions. Because Merge Sort doubles the number of sub-problems while halving their size at each level, it is incredibly efficient for large data sets compared to Selection Sort or Insertion Sort.

  • Merge Sort: Efficient for large data sets but requires more memory (to hold the temporary arrays during merging).
  • Recursive nature: The mergeSort method calls itself twice (once for the left half, once for the right half) and then calls a merge helper method.

3. Tracing Recursive Algorithms

One of the most common tasks on the AP Exam is tracing a recursive method to see how it affects a String, an array, or an ArrayList. When tracing, it is helpful to use a Recursion Tree.

How to Trace a Recursive Search/Sort:

  1. Identify the Base Case: What condition stops the recursion? (e.g., \( low > high \) or \( array.length < 2 \)).
  2. Track the Parameters: Write down the values of the variables (like \( low \), \( high \), and \( mid \)) for every single call.
  3. Follow the Stack: Remember that a recursive call must finish completely before the original method can continue its next line of code.

Example Trace Concept: If you call Merge Sort on an array of 4 elements:
1. It calls itself for the first 2 elements.
2. That call calls itself for the 1st element (Base Case - returns).
3. Then it calls itself for the 2nd element (Base Case - returns).
4. Only then does it "Merge" the 1st and 2nd elements together.

4. Common Pitfalls and Tips

The "Infinite Recursion" Trap: If the recursive step doesn't move toward the base case (for example, if \( mid \) is calculated incorrectly), the program will result in a StackOverflowError.

Did you know? Binary Search is so efficient that you could find a specific person out of 7 billion people on Earth in about 33 steps or fewer, provided they were all sorted in a list!

Key Takeaways for the Exam:
- Binary Search starts at the middle and eliminates half the collection each step.
- Merge Sort is recursive; it splits data down to individual items and then merges them back in order.
- Binary Search can be written using a loop (iteratively) or using recursion.
- Always check if the data is sorted before assuming Binary Search will work.
- You will be asked to analyze or trace these algorithms, not write them from scratch.