Recursive Searching and Sorting

Using recursion, we can make our searching and sorting algorithms from Unit 7 much more concise, and we will also have new searching and sorting algorithms that may be more efficient than our previous algorithms!

#Searching - Linear/Sequential Search

We already covered this iteratively in Topic 7.5. As a reminder, here is the iterative code:

public static int linearSearch(ArrayList<Integer> array, int n) {
for (int i = 0; i < array.size(); i++) {
if (array.get(i) == n) {
return i;
}
}
return -1;
}

Here is the recursive version:

public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
if (array.get(startingIndex) == n) {
return startingIndex; // base case #1: element found
} else if (startingIndex == array.size() - 1) {
return -1; //base case #2: element not found
} else {
//recursive call to check next element
return recursiveLinearSearch(array, n, startingIndex + 1);
}
}

//To use this method:
recursiveLinearSearch(array, n, 0);

#Searching - Binary Search

Binary search is the new search algorithm that we'll learn in this unit, and it is quicker than linear sort. However, the tradeoff for the speed is that the list has to be presorted. Binary search will not work if the data is not presorted.

Here is its implementation, along with how it works both iteratively and recursively:

/** Uses binary search on a sorted ArrayList
*   1. Looks at the middle of the list, which divides it into two sublists
*   2. The left sublist is less than the middle and the right is greater
*   3. Compare the value to be searched for to the middle value
*   4. If this value > middle, repeat 1-3 to the right sublist
*   5. If this value < middle, repeat 1-3 to the left sublist
*   6. If this value = middle, return the middle value
*   7. Return -1 if value not found
*/
public static int binarySearch(ArrayList<Integer> array, int n) {
int left = 0;
int right = array.size() - 1;
while (left <= right) { // left > right is "illegal"
int middle = (left + right) / 2; // get the middle index of sublist
if (n == array.get(middle)) { // item in middle of sublist
return middle;
} else if (n < array.get(middle)) { // item in left sublist
right = middle - 1;
} else if (n > array.get(middle)) { // item in right sublist, could just use else
left = middle + 1;
}
}
return -1; // item not in list
}

public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
int middle = (left + right) / 2; // get the middle index of sublist
if (left > right) { // base case #1: item not in list
return -1;
} else if (n == array.get(middle)) { // base case #2: item in middle of sublist
return middle;
} else if (n < array.get(middle)) { // recursive call #1: item in left sublist
return recursiveBinarySearch(array, n, left, middle - 1);
} else if (n > array.get(middle)) { // recursive call #2: item in right sublist, could just use else
return recursiveBinarySearch(array, n, middle + 1, right);
}
}

//To use this, call:
recursiveBinarySearch(array, n, 0, array.size() -1);

Here is a visualization of binary search:

#Courtesy of Study.com.

#Sorting - Insertion Sort

We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:

/** Uses insertion sort on an ArrayList
*   1. Assume the first element i...