Problem: We discussed in the lectures how to write a linear search algorithm using a for loop which iterates over each element of a list. Linear search can also be implemented recursively. For this exercise, write a recursive method int recLinearSearch(ArrayList pList, String pKey, int pBeginIdx, int pEndIdx) that searches pList elements pBeginIdx up to and including pEndIdx for pKey and returns the index of pKey in pList if found or -1 if not found. Hint: The base case is reached when pBeginIdx is greater than pEndIdx (what does this mean?). Otherwise, check to see if the element at pBeginIdx is equal to pKey. If it is, then return pBeginIdx. If it is not, then make a recursive method call which will search pList at elements pBeginIdx + 1 to pEndIdx. Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than Hw4_41. For testing, your method will be called in this manner to search the entire list: ArrayList list = new ArrayList<>(); // populate list with some Strings... int idx = recLinearSearch(list, "the key", 0, list.size() - 1); Note that if list is empty, the method should return -1.

4.2 Learning Objective: For the student to demonstrate that he or she understands how the recursive binary search algorithm works. Instructions: This question is not graded, but if you wish, you may include your solution in your word processing document. Problem: Suppose list is an ArrayList of Integers and contains these elements (note that list is sorted in ascending order); list = { 2, 3, 5, 10, 16, 24, 32, 48, 96, 120, 240, 360, 800, 1600 } and we call the recursive binary search method from the lecture notes: int index = recursiveBinarySearch(list, 10, 0, list.size() - 1); where 10 is the key, 0 is the index of the first element in the range of list that we are searching (this is pLow), and list.size() - 1 is the index of the last element in the range of list that we are searching (this is pHigh). Trace the method by hand and show the following: (1) The values of pLow and pHigh on entry to each method call; (2) The value of pMiddle that is computed; (3) State which clause of the if-elseif-elseif statement will be executed, i.e., specify if return middle; will be executed, or if return recursiveBinarySearch(pList, pKey, pLow, middle - 1); will be executed, or if return recursiveBinarySearch(pList, pKey, middle + 1, pHigh); will be executed; (4) After the method returns, specify the value assigned to index and the total number of times that recursiveBin arySearch() was called, including the original call shown above.

4.3 Repeat Exercise 4.2 but this time let pKey be 150. This exercise is graded, so include your trace in the word processing document.