TOPIC 4.17 · STUDY

Recursive Searching and Sorting

Recursive helpers walk a string or collection by shrinking the problem until a base case. Binary search on sorted data compares the middle index and keeps only the half that can still hold the target. mergeSort splits until each piece has one element, then merges sorted halves back together.

4.17.A

Recursive algorithms on strings and collections

Topic 4.17 starts by tracing recursive methods that process a String or a collection. Each call must shrink the remaining work, reach a base case, and combine or return a result. One common pattern compares the ends of a string and stops as soon as those ends disagree.

sameEnds returns true when every paired outer pair matches. If the string is empty or has one character, the answer is true. Otherwise compare the first character to the last. A mismatch returns false immediately, with no further recursive call. A match peels both ends and continues on the shorter middle.

public static boolean sameEnds(String s)
{
    if (s.length() <= 1)
    {
        return true;
    }
    if (!s.substring(0, 1).equals(s.substring(s.length() - 1)))
    {
        return false;
    }
    return sameEnds(s.substring(1, s.length() - 1));
}

System.out.print(sameEnds("radar") + " " + sameEnds("raft"));
// true false

sameEnds("radar") matches r with r, then a with a, then reaches the one-letter middle d and returns true. sameEnds("raft") compares r with t, finds a mismatch, and returns false without looking at the middle letters. The early false return is the whole point of this search: once a pair fails, deeper calls cannot repair it.

Key points

  • Trace recursive string or collection methods by naming the smaller argument each call passes.
  • A base case for length 0 or 1 stops sameEnds with true.
  • A first-and-last mismatch returns false with no further recursive call.
  • Matching ends shrink the string with substring(1, length - 1) and continue.
  • Early failure means later middle characters are never examined.

4.17.B

Recursive binary search

Binary search looks for a target in a collection that is already sorted from smallest to largest. The helper hunt(data, target, low, high) works on the inclusive index range from low through high. If low is greater than high, the range is empty and the method returns -1.

Otherwise mid is (low + high) / 2 using integer division. If data[mid] equals the target, return mid. If data[mid] is less than the target, search only mid + 1 through high. If data[mid] is greater than the target, search only low through mid - 1. Each step drops about half of the remaining indexes.

public static int hunt(int[] data, int target, int low, int high)
{
    if (low > high)
    {
        return -1;
    }
    int mid = (low + high) / 2;
    if (data[mid] == target)
    {
        return mid;
    }
    else if (data[mid] < target)
    {
        return hunt(data, target, mid + 1, high);
    }
    else
    {
        return hunt(data, target, low, mid - 1);
    }
}

int[] gates = {8, 15, 22, 29, 36, 43, 50};
System.out.print(hunt(gates, 36, 0, 6));
// 4

For target 36 with low 0 and high 6, the first mid is 3 and data[3] is 29, which is smaller than 36, so the next range is 4 through 6. The next mid is 5 and data[5] is 43, which is larger, so the next range is 4 through 4. That mid is 4 and data[4] is 36, so hunt returns 4.

Three boxes labeled low, mid, and high show indexes 4, 5, and 6 after the first binary-search step moves past 29.

After discarding 29, the live range is indexes 4 through 6. mid is 5; because 43 is too large, the next call keeps only low through mid - 1.

Key points

  • Binary search requires data already sorted in increasing order.
  • If low > high, return -1 without computing mid.
  • mid is (low + high) / 2; a match returns that index.
  • A middle value below the target searches mid + 1 through high.
  • A middle value above the target searches low through mid - 1.

4.17.C

Merge sort

mergeSort rearranges a range by dividing, not by selection or insertion passes. While from is less than to, mid is (from + to) / 2. The method sorts from through mid, sorts mid + 1 through to, then merges those two already-sorted halves into one ordered range.

Division continues until every piece has a single element. A one-element list is already sorted. Merging repeatedly takes the smaller front value from the two halves until both halves are empty. For a four-element start, the first split uses mid = (0 + 3) / 2 = 1, so the halves are indexes 0..1 and 2..3.

public static void mergeSort(int[] data, int from, int to)
{
    if (from < to)
    {
        int mid = (from + to) / 2;
        mergeSort(data, from, mid);
        mergeSort(data, mid + 1, to);
        merge(data, from, mid, to);
    }
}

// First split of {27, 6, 14, 3} with from 0 and to 3:
// left  {27, 6}
// right {14, 3}

After deeper splits, the one-element pieces are {27}, {6}, {14}, and {3}. Merging each pair produces the sorted halves {6, 27} and {3, 14}. The final merge of those halves yields {3, 6, 14, 27}. Exam items often ask for the first split or the sorted halves just before the last merge, not only the finished array.

Key points

  • mergeSort splits the range in half while from < to.
  • mid is (from + to) / 2; left is from..mid and right is mid+1..to.
  • A one-element piece needs no further split.
  • After both halves are sorted, merge combines them in order.
  • For four elements, the first split is two pairs, not the final sorted list.

Binary search is only valid on sorted data. Discarding half the range after a middle comparison is unsafe if the values are out of order.

Practice this topic