01 / 21

Recursive Searching
and Sorting

Master binary search and merge sort through the lens of recursion: breaking big problems into smaller, self-similar subproblems.

AP Computer Science A

What is Recursion?

A recursive method is one that calls itself to solve a smaller instance of the same problem. Every recursive solution has two critical parts:

Base Case
The simplest version of the problem that can be solved directly, without further recursion. It stops the chain of calls.
Recursive Case
The method calls itself with a smaller or simpler input, making progress toward the base case with every call.

Why Recursion for Search and Sort?

Many searching and sorting algorithms naturally follow a divide-and-conquer strategy: split the problem, solve each piece recursively, then combine the results.

1
Divide: break the data into smaller sub-arrays.
2
Conquer: recursively solve each sub-array.
3
Combine: merge or select results from sub-problems.

The Call Stack in Action

Each recursive call creates a new stack frame. When a base case returns, frames unwind in reverse order. Understanding this is key to tracing recursive algorithms.

search(arr, 0, 15, key) search(arr, 8, 15, key) search(arr, 8, 10, key) Base case: arr[9] == key return Call 1 Call 2 Call 3 Call 4 Stack grows down, returns unwind up

Recursive Binary Search

Given a sorted array, binary search finds a target by repeatedly halving the search range. Its time complexity is \( O(\log n) \).

public static int binarySearch(int[] arr, int lo, int hi, int key) { if (lo > hi) return -1; // base case: not found int mid = (lo + hi) / 2; if (arr[mid] == key) return mid; // base case: found else if (arr[mid] < key) return binarySearch(arr, mid+1, hi, key); else return binarySearch(arr, lo, mid-1, key); }

Binary Search: Step by Step

Searching for 23 in a sorted array of 8 elements:

Step 1: lo=0, hi=7, mid=3 2 5 8 12 23 30 42 55 mid=3, arr[3]=12 12 < 23, go right Step 2: lo=4, hi=7, mid=5 23 30 42 55 mid=5, arr[5]=30 30 > 23, go left Step 3: lo=4, hi=4, mid=4 23 arr[4]=23 = key Found at index 4!

A sorted collection makes discarded search ranges meaningful

An archivist opens a specimen drawer beside unordered return trays.Sorted order makes it possible to discard an entire search range after one comparison. An unsorted collection does not support the same elimination.

Binary search with Java indices

Three rows highlight midpoint indices 4, 6 and 5 as excluded values fade.Search this sorted nine-value array for 23. The tested midpoint values are 17, 31 and 23; Java indices 0 through 8 lead to a return value of 5. Each failed comparison excludes its tested midpoint.

Count comparisons as the list grows

A step graph plots the exact worst-case binary-search probe count against list size on a log₂ horizontal axis.For inclusive midpoint binary search on n ≥ 1 items, the maximum number of probes is floor(log₂ n) + 1. The horizontal axis uses a log₂ scale; the count measures search probes after sorting.

Recursive Merge Sort

Merge sort splits the array into halves, recursively sorts each half, then merges them into sorted order. Time complexity: \( O(n \log n) \).

public static void mergeSort(int[] arr, int lo, int hi) { if (lo >= hi) return; // base case: 0 or 1 elements int mid = (lo + hi) / 2; mergeSort(arr, lo, mid); // sort left half mergeSort(arr, mid+1, hi); // sort right half merge(arr, lo, mid, hi); // merge the two halves }

Merge Sort: Split and Merge

38 27 43 3 9 82 10 Split 38 27 43 3 9 82 10 38 27 43 3 9 82 10 Base cases (single elements) Merge up 27 38 3 43 9 82 10 3 9 10 27 38 43 82 Fully sorted

The Merge Helper Method

The merge method combines two already-sorted halves into one sorted sequence using a temporary array.

1
Create a temp array to hold the merged result.
2
Use two pointers: one for each half. Compare front elements, copy the smaller one into temp.
3
Copy remaining elements from whichever half is not yet exhausted.
4
Copy temp back into the original array at the correct positions.

Binary vs Linear Search

Binary Search Linear Search
Precondition Array must be sorted No requirement
Time Complexity \( O(\log n) \) \( O(n) \)
Strategy Divide and conquer Check every element
Recursive? Naturally recursive Typically iterative
Best for Large sorted datasets Small or unsorted data

Merge Sort vs Selection Sort

Merge Sort Selection Sort
Time (worst) \( O(n \log n) \) \( O(n^2) \)
Time (best) \( O(n \log n) \) \( O(n^2) \)
Space \( O(n) \) extra (temp array) \( O(1) \) in-place
Strategy Divide and conquer Find minimum, swap
Recursive? Yes No (iterative)

How to Apply Binary Search

1
Confirm the array is sorted. Binary search will produce wrong results on unsorted data.
2
Set \( \text{lo} = 0 \) and \( \text{hi} = \text{arr.length} - 1 \). These define the current search range.
3
Compute \( \text{mid} = (\text{lo} + \text{hi}) / 2 \). Compare \( \text{arr}[\text{mid}] \) with the target.
4
If equal, return mid. If target is greater, recurse on the right half (\( \text{mid}+1, \text{hi} \)). If lesser, recurse on the left half (\( \text{lo}, \text{mid}-1 \)).
5
If \( \text{lo} > \text{hi} \), return -1. The target is not in the array.

Example: Trace Binary Search

Array: {1, 4, 7, 10, 15, 20, 25}. Find 15.

1
\( \text{lo}=0, \text{hi}=6, \text{mid}=3 \). \( \text{arr}[3]= \)10. Since \( 10 < 15 \), search right: \( \text{lo}=4, \text{hi}=6 \).
2
\( \text{lo}=4, \text{hi}=6, \text{mid}=5 \). \( \text{arr}[5]= \)20. Since \( 20 > 15 \), search left: \( \text{lo}=4, \text{hi}=4 \).
3
\( \text{lo}=4, \text{hi}=4, \text{mid}=4 \). \( \text{arr}[4]= \)15. Found! Return index 4.

Example: Trace Merge Sort

Sort {5, 2, 8, 1} using merge sort.

1
Split: {5, 2} and {8, 1}.
2
Split {5, 2}: {5} and {2}. Both base cases. Merge: {2, 5}.
3
Split {8, 1}: {8} and {1}. Both base cases. Merge: {1, 8}.
4
Final merge: {2, 5} and {1, 8}. Compare 2 vs 1: take 1. Compare 2 vs 8: take 2. Compare 5 vs 8: take 5. Take 8. Result: {1, 2, 5, 8}.

Example: Merge in Detail

Merge left = {3, 9, 27} and right = {10, 38, 43} step by step.

Left 3 9 27 Right 10 38 43 Merged (temp) 3 < 10 3 9 < 10 9 27 > 10 10 27 < 38 27 Copy rest 38 Result: 3 9 10 27 38 43

Common Mistakes

Missing Base Case
Forgetting the base case causes infinite recursion and a StackOverflowError. Always check for the simplest case first.
Off-by-One Errors
Incorrectly updating bounds for the recursive call (e.g., using \( \text{mid} \) instead of \( \text{mid}+1 \) or \( \text{mid}-1 \)) can cause an infinite loop or skip the target.
Unsorted Array
Running binary search on an unsorted array produces incorrect results. Always verify the precondition.

Question 1 of 5

What is the time complexity of recursive binary search on a sorted array of \( n \) elements?

Question 2 of 5

In the recursive binary search method, what happens when \( \text{lo} > \text{hi} \)?

Question 3 of 5

What is the base case for merge sort?

Question 4 of 5

Consider the array {2, 5, 8, 12, 15, 18, 23}. How many total calls to binarySearch are needed to find 18?

Question 5 of 5

What is the space complexity of merge sort and why?