RULES:

You may not make use of any Java classes other than incidental use of Strings, calls to System.out.println, and accessing an existing array passed to your method. The tester program will verify that your program contains no imports, no use of new, and the only uses of . (dot) are within calls to System.out.println, accessing array .length, or followed by a digit (double literals).

You may not use for or while. Any looping must be accomplished using recursion. The testerprogram will check for no fors or whiles and may be triggered by the word in a comment.

You may not declare static or non-static member fields only local or parameter variables allowed.

You may implement additional helper methods to use the recursive driver technique as we did with the find method in class.

Part 3. Recursive approximate median (30 pts) Consider an array of integers. You wish to find an approximate median. You have an idea: split the array (or a range of the array) into three pieces, find the approximate median of each piece, and then return the actual median of the three approximate medians (if you put the three approximate medians in sorted order, the one in the middle). There are a few details to consider. If we are trying to find the approximate median of a range consisting of one element, that element itself is its own median. If the range contains two elements, take the mean (average) which may be a fractional value. Otherwise, the range contains at least three elements and we can split it into three pieces. The length of the range may be divisible by 3, have a remainder of 1 when divided by 3, or a remainder of 2 when divided by 3. If the range length has a remainder of 0 when divided by 3: each piece should be n/3 elements. if a remainder of 1: the first piece should consist of the first [n/3] elements, the last piece should consist of the last In/3] elements, and the middle piece is the remaining [n/3] elements. [n/3] rounds up (For example, if there were 4 elements, the first piece is the first element, the last piece is the last element, and the middle two elements constitute the middle piece.) if a remainder of 2: the first piece should consist of the first [n/3] elements, the last piece should consist of the last [n/31 elements, and the middle piece is the remaining [n/3] elements. (For example, if there were 8 elements, the first piece is the first 3 elements, the last piece is the last 3, and the middle two elements constitute the middle piece.) Implement the method public static double median3(int[] a) that follows the above strategy. Do not create any new arrays; you will need one or more helper methods that look at portions/ranges/pieces of the existing array. Do not modify the array you are given. Examples, where the square braces show the elements in each recursive call's range: int[] a - [1j; median3(a); // returns 1.0 int[] b -f1, 2}; median3(b); // return 1.5 int c = {3, -10 , 100}; median3 (c); // returns 3 int[] d -f1, 2, -5, 10, 100, 6}; median3 (d); // median of [1, 2], [-5, 10], [100, 6]: returns 2.5 inti e- {1, 2, -10. 7. 20, -3, 100 , 6); median3 (e); // [[1], [2], [-10]], [7, 20], [-3], [100], [6]]: returns 6 int[] f-1, 2, -20, -10, 7, 20, -3, 100, 6, 92}; median3 (f); //I[1],[2], [-20]], [[-10], [7,20], [-3]], [[10], [6], [92]]: 1.0