Modify the search code given in the lecture for recursive linear search (given below). Write a recursive linear search method that works on sorted data. The method header is:

public static int linearSortedOptimizedRecursiveSearch(Comparable[] data, Comparable target)

Note this is a linear search- not a binary search!

Your code should differ from the provided code in the following ways:

return the index (the location of the element) instead of a boolean

the code will work on Comparable objects (instead of Object)

add optimization so that the linear search for an element that isn't in the array stops once you know that's the case (you can refer to the similar improvement made to the iterative version)

boolean linearSearch(int first, int last, Object[] data, Object target) { if(first > last) { return false; } else if(target.equals(data[first])) { return true; } else { return linearSearch(first+1, last, target, data); } }