10.2 Recursive Searching and Sorting

Searching and sorting are fundamental operations in computer science, and recursion provides elegant solutions for both. This study guide explores how recursion can be applied to create efficient search algorithms like binary search and powerful sorting algorithms like merge sort. These recursive approaches demonstrate how complex problems can be broken down into simpler subproblems to achieve efficient solutions.

Binary Search: Divide and Conquer

Binary search is an efficient algorithm for finding a target value in a sorted collection. Unlike sequential search (checking each element one by one), binary search eliminates half of the remaining elements in each step.

Key Requirements for Binary Search

• The data must be sorted before using binary search
• Works with String, arrays, or ArrayLists

How Binary Search Works

1. Find the middle element of the collection
2. Compare the middle element with the target value
3. If they match, we've found the target
4. If the target is less than the middle, search the left half
5. If the target is greater than the middle, search the right half
6. Repeat until the target is found or the search space is empty

Recursive Binary Search Implementation

public static int binarySearch(int[] arr, int target, int left, int right) {
    // Base case: element not found
    if (left > right) {
        return -1;
    }
    
    // Find middle index
    int mid = (left + right) / 2;
    
    // Base case: element found
    if (arr[mid] == target) {
        return mid;
    }
    // Recursive case: search left half
    else if (target < arr[mid]) {
        return binarySearch(arr, target, left, mid - 1);
    }
    // Recursive case: search right half
    else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

// Initial call
int index = binarySearch(myArray, targetValue, 0, myArray.length - 1);

Binary Search with ArrayList

public static int binarySearch(ArrayList<Integer> list, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = (left + right) / 2;
    
    if (list.get(mid) == target) {
        return mid;
    }
    else if (target < list.get(mid)) {
        return binarySearch(list, target, left, mid - 1);
    }
    else {
        return binarySearch(list, target, mid + 1, right);
    }
}

Binary Search with Strings

public static int binarySearch(String[] arr, String target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = (left + right) / 2;
    
    int comparison = target.compareTo(arr[mid]);
    
    if (comparison == 0) {
        return mid;  // Found it!
    }
    else if (comparison < 0) {
        return binarySearch(arr, target, left, mid - 1);  // Search left
    }
    else {
        return binarySearch(arr, target, mid + 1, right);  // Search right
    }
}

Binary Search Efficiency

For large datasets, the efficiency improvement is dramatic:

Tracing a Binary Search

Let's trace the execution of binary search on the array [10, 20, 30, 40, 50, 60, 70] looking for the value 30:

Merge Sort: Divide, Sort, and Merge

Merge sort is a recursive sorting algorithm that follows the divide-and-conquer approach:

1. Divide: Split the array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the sorted halves

Merge Sort Implementation

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = (left + right) / 2;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    // Calculate sizes of subarrays
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temporary arrays
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];
    
    // Copy data to temp arrays
    for (int i = 0; i < n1; ++i)
        leftArray[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        rightArray[j] = arr[mid + 1 + j];
    
    // Merge temp arrays
    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }
    
    // Copy remaining elements
    while (i < n1) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

// Initial call
mergeSort(myArray, 0, myArray.length - 1);

Merge Sort with ArrayList

public static void mergeSort(ArrayList<Integer> list, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(list, left, mid);
        mergeSort(list, mid + 1, right);
        
        merge(list, left, mid, right);
    }
}

private static void merge(ArrayList<Integer> list, int left, int mid, int right) {
    // Create temporary lists
    ArrayList<Integer> leftList = new ArrayList<>();
    ArrayList<Integer> rightList = new ArrayList<>();
    
    // Copy data to temp lists
    for (int i = left; i <= mid; i++)
        leftList.add(list.get(i));
    for (int i = mid + 1; i <= right; i++)
        rightList.add(list.get(i));
    
    // Merge temp lists
    int i = 0, j = 0, k = left;
    while (i < leftList.size() && j < rightList.size()) {
        if (leftList.get(i) <= rightList.get(j)) {
            list.set(k, leftList.get(i));
            i++;
        } else {
            list.set(k, rightList.get(j));
            j++;
        }
        k++;
    }
    
    // Copy remaining elements
    while (i < leftList.size()) {
        list.set(k, leftList.get(i));
        i++;
        k++;
    }
    while (j < rightList.size()) {
        list.set(k, rightList.get(j));
        j++;
        k++;
    }
}

Visualizing Merge Sort

For the array [38, 27, 43, 3, 9, 82, 10]:

1. Divide the array into [38, 27, 43, 3] and [9, 82, 10]
2. Divide again: [38, 27], [43, 3], [9, 82], [10]
3. Divide once more: [38], [27], [43], [3], [9], [82], [10]
4. Merge sorted arrays: [27, 38], [3, 43], [9, 82], [10]
5. Merge again: [3, 27, 38, 43], [9, 10, 82]
6. Final merge: [3, 9, 10, 27, 38, 43, 82]

Merge Sort Efficiency

For large datasets, the efficiency gain is significant:

Iterative vs. Recursive Implementations

Both binary search and merge sort can be implemented iteratively or recursively:

Binary Search:

// Iterative binary search
public static int binarySearchIterative(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        else if (target < arr[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    
    return -1;
}

The recursive version can be more elegant, but both approaches have the same time complexity. The iterative version uses constant space, while the recursive version uses O(log n) space for the call stack.

Summary

Recursive searching and sorting algorithms demonstrate the power of the divide-and-conquer approach in computer science. Binary search provides efficient lookup in sorted collections by eliminating half of the remaining elements in each step, achieving logarithmic time complexity. Merge sort offers efficient sorting through recursive division and merging, achieving linearithmic time complexity. Both algorithms can be implemented recursively or iteratively, with recursive implementations often providing more elegant and intuitive solutions at the cost of additional memory usage for the call stack. These algorithms showcase how recursion can be applied to solve complex problems by breaking them down into simpler subproblems.