Recursive Searching and Sorting

Hey everyone, it's Saavi. Let's dive into two of the most elegant ideas in computer science. They might feel a little abstract at first, but once you see the pattern, you'll appreciate how clever and powerful they are.

Recursion on Collections

Before we get to the big algorithms, let's quickly refresh how recursion works on data collections like String objects or arrays. Remember, a recursive solution has two parts:

1. 1
   Base Case

   The simplest possible problem that can be solved directly, which stops the recursion.
2. 2
   Recursive Step

   The part that breaks the problem into a smaller version of itself and calls the method again on that smaller piece.

For example, you could write a recursive method to check if a word is a palindrome. The base case might be a word with 0 or 1 letters (which is always a palindrome). The recursive step would check if the first and last letters match, and if they do, you'd recursively call the method on the substring without those letters. This idea of breaking a collection down is fundamental to what follows.

Binary Search: The Smartest Guessing Game

Binary search is your go-to algorithm for finding an element in a sorted collection. I can't stress that enough.

The Golden Rule: Binary search only works on sorted data. If you try to run it on an unsorted array of numbers from a basketball game's stats, you'll get incorrect results or miss the value entirely. Why? Because the whole algorithm relies on being able to eliminate half the data based on a comparison, just like with the dictionary example.

Here's how it works on a sorted array:

1. 1
   Find the middle

   You look at the element right in the middle of the array.
2. 2
   Compare

   • Is this the element you're looking for? If yes, you're done! That's a base case.
   • Is your target value smaller than the middle element? If yes, you know it must be in the left half. You can completely ignore the right half.
   • Is your target value larger than the middle element? If yes, you know it must be in the right half. You can ignore the left half.
3. 3
   Recurse

   You repeat the process on the remaining half of the array.

This process continues until you either find the element or the search space runs out (meaning the element isn't in the array). Each step cuts your search space in half, which makes it incredibly fast—much more efficient than checking every single element one by one (linear search).

While you can write binary search with a while loop (iteratively), the recursive version is a beautiful demonstration of a "divide and conquer" strategy.

// A conceptual look at recursive binary search
public int binarySearch(int[] arr, int target, int low, int high) {
    if (low > high) {
        return -1; // Base case: not found
    }

    int mid = low + (high - low) / 2; // Avoids potential overflow

    if (arr[mid] == target) {
        return mid; // Base case: found!
    } else if (target < arr[mid]) {
        // Recursive step: search the left half
        return binarySearch(arr, target, low, mid - 1);
    } else {
        // Recursive step: search the right half
        return binarySearch(arr, target, mid + 1, high);
    }
}

Merge Sort: Divide, Conquer, and Combine

What if your data isn't sorted? You need an efficient way to sort it. Enter Merge Sort.

Merge sort is a recursive sorting algorithm that is famous for its reliability and efficiency. It follows the "divide and conquer" mantra perfectly.

That's the Divide step. Merge sort recursively splits the array in half until it's broken down into a series of one-element arrays.

[8, 3, 5, 1] -> [8, 3] and [5, 1] -> [8], [3], [5], [1]

Now comes the Conquer (or Merge) step. This is the real work. Starting with those single-element arrays, you merge them back together in sorted order.

1. You take two adjacent "piles" (which are already sorted) and a new, empty "pile".
2. You look at the top form of each pile. Whichever comes first alphabetically, you move it to your new, merged pile.
3. You repeat this, always comparing the top forms of your two source piles, until one pile is empty.
4. Then, you just add the rest of the remaining pile to the end of your new pile.

You repeat this merging process up the chain. The two-form piles get merged into sorted four-form piles, which get merged into sorted eight-form piles, and so on, until you have one, big, perfectly sorted stack of forms.

Merge sort is a workhorse. It's more predictable than other sorting algorithms you might see later, and its efficiency is a benchmark for sorting.

Let's trace these algorithms so you can see them in action. Tracing is a critical skill for the AP exam.

Ready to try it yourself? Grab a piece of paper and trace the logic.

Problem 1: Binary Search Practice You have a sorted ArrayList of product IDs from a warehouse in Dallas: [101, 115, 132, 247, 301, 302, 450, 489, 512].

Trace the steps of a recursive binary search to find the product with ID 450. Keep track of the low, high, and mid indices for each recursive call. What are they for the second recursive call?

Problem 2: Merge Sort Practice You're given an array of unsorted scores from a school's soccer tryouts: [88, 75, 92, 81, 79, 95].

Show the result of the first merge operation that would happen after the array is completely split. Then, show the result of merging [75, 88] and [81, 92] together.