Sorting and Searching

Given the following code, implement a recursive BinarySearcher method as a helper to find the indexOf a particular element. (It should return -1 if the element is not found):

import java.util.List; import java.lang.Comparable; import java.util.ArrayList; public class Sorter {

public static > void bubbleSort(List theList) { int lastToConsider = theList.size(); while (lastToConsider > 1) { for (int j=0; j 0 ) { swap(theList,j,j+1); } } lastToConsider--; } } // End method bubbleSort

private static > void swap(List theList, int i1, int i2) { T temp = theList.get(i1); theList.set(i1,theList.get(i2)); theList.set(i2,temp); } // End method swap

public static > void selectionSort(List theList) { // Loop over theList.size() - 1 for (int index = 0; index < theList.size() - 1; index++) { int min = index; // First index // Loop to find minimum for (int scan = index + 1; scan < theList.size(); scan++) if (theList.get(scan).compareTo(theList.get(min)) < 0) min = scan;

swap(theList, min, index); // Swap the values } } // End method selectionSort

public static > void mergeSort(List theList) { recursiveMergeSortHelper(theList,0,theList.size()); } // End method mergeSort

private static > void recursiveMergeSortHelper(List theList, int first, int last) { // Test base case int size = last - first; if (size <= 1) return; int mid = first + size/2; recursiveMergeSortHelper(theList, first, mid); recursiveMergeSortHelper(theList, mid, last);

List temp = new ArrayList<>(); int i = first, j = mid; for (int k = 0; k < size; k++) { if (i == mid) temp.add(theList.get(j++)); else if (j == last) temp.add(theList.get(i++)); else if (theList.get(j).compareTo(theList.get(i)) < 0) temp.add(theList.get(j++)); else temp.add(theList.get(i++)); } for (int k = 0; k < size; k++) theList.set(first + k, temp.get(k)); } // End method recursiveMergeSortHelper

public static > int indexOf(T searchItem, List theList) { return recursiveBinarySearcher(searchItem, theList, 0, theList.size()); } // End method indexOf private static > int recursiveBinarySearcher(T searchItem, List theList, int first, int last) { // stubbed } // End method recursiveBinarySearcher } // End class Sorter