Please include the following header for each Java program: /********************************************************************* Purpose/Description:

Problem #1: (25 points) (a) Implement a recursive search function in Java int terSearch(int arr[l, int I, int r, int x) that returns location of x in a given sorted array arr[I... ] is present, otherwise -1. The terSearch search function, unlike the binary search, must consider two dividing points int d1I + (r- /3 int d2 = d1 + (r-1)/3 (b) What is the running time complexity of your function? Justify. Problem #2: (25 points) 2. Given two sorted lists, L1 and L2, complete a following procedure in Java to compute: (a) L1 ?L2 = { x | x e L1 and X E L2 } using only the basic list operators (next(), hasNext(), and compareTo)) and one loop. public static > void difference(List L1, List L2, List iterL1 - L1.listIterator() ListIterator iterL2 -L2.listIteratorO if (iterL1.hasNext() && iterL2.hasNext ()) item L1 = iterL1.next(); itemL2 iterL2.next ); //YOUR CODE GOES HERE