Recursive Searching and Sorting

Introduction: 10.2.0

• You can do searching and sorting using recursion
  • You can do binary search and merge-sort using recursion

Recursive Binary Search: 10.2.1

• Linear searches for an element check each item until the item is found
• Binary search is more efficient because it eliminates half of the array every pass
  • It only works on sorted data
  • It can be written iteratively or recursively

public int iterativeBinarySearch(int[] elements, int target) {
  int min = 0;
  int max = elements.length - 1;
  
  while (min <= max) {
    middle = (max + min)/2;
    if (target < elements[middle]) {
      right = middle - 1;
    } else if (target > elements[middle]) {
      left = middle + 1;
    } else {
      return middle;
    }
  }
  return -1;  // not found!
}


public int recursiveBinarySearch(int[] elements, int target, int min, int max) {
  int middle = (max + min)/2;
  
  if (end < start) {
    return -1;
  }
  
  if(target == elements[middle]) {
    return middle;
  }
  
  if (target < elements[middle]) {
    return recursiveBinarySearch(elements, target, min, middle-1);
  }
  
  if (target > elements[middle]) {
    return recursiveBinarySearch(elements, target, middle+1, max);
  }
  
  return -1;
}

Merge Sort: 10.2.2

• Merge sort is a sorting algorithm which uses recursion
• It divides the problem in half like binary search
  • Divide and conquer!
  • This makes it generally faster than other sorting algorithms
• A merge sort breaks the values to sort down until you only have one value, then merges the sorted lists back together
• Left, Right, Merge!
  • mergeSort the left side
  • mergeSort the right side
  • merge the sorted sides together
  • Because arrays are references, the sorts work their way up to the original array automatically!
• Merging
  • copy original elements to a temporary array
    • think of the temporary array as two virtual arrays
  • work from left to right in each virtual array
  • This is iterative, not recursive
    • Stop conditions:
      • The leftmost pointer enters the right side
        • The right side is already sorted!
      • The rightmost pointer is == length
        • return the left side into the array in order
  • compare elements to return them to the original array in order
• On the AP Exam, identify a merge sort using the following:
  • 3 methods: mergeSort, mergeSortHelper, and merge
  • mergeSortHelper is recursive

This is a very complicated topic, and I found it incredibly helpful to watch the AP Classroom videos here.
I tried to take some notes from there into here, but it really is a visual thing (at least for me).

public static void mergeSort(int[] elements)
{
   int n = elements.length;
   int[] temp = new int[n];
   mergeSortHelper(elements, 0, n - 1, temp);
}

private static void mergeSortHelper(int[] elements, int from, int to, int[] temp)
{
    if (from < to)
    {
       int middle = (from + to) / 2;
       mergeSortHelper(elements, from, middle, temp);
       mergeSortHelper(elements, middle + 1, to, temp);
       merge(elements, from, middle, to, temp);
    }
}
private static void merge(int[] elements, int from, int mid, int to, int[] temp)
{
   int i = from;
   int j = mid + 1;
   int k = from;
 while (i <= mid && j <= to)
   {
      if (elements[i] < elements[j])
       {
         temp[k] = elements[i];
         i++;
      }
      else
      {
         temp[k] = elements[j];
         j++;
      }
      k++;
   }
 while (i <= mid)
   {
      temp[k] = elements[i];
      i++;
      k++;
   }
 while (j <= to)
   {
      temp[k] = elements[j];
      j++;
      k++;
   }
 for (k = from; k <= to; k++)
   {
      elements[k] = temp[k];
   }
}

Summary: 10.2.4

• Binary search can be written either iteratively or recursively
• Data must be sorted to use binary search
• The binary search algorithm starts at the middle of a sorted array and eliminates half of the array each iteration
  • This makes it significantly faster than linear search
• Merge sort is a recursive sorting algorithm which can sort elements in an array or arraylist