Question 1 Write a Java program called LinearSearch.java that uses a static method to search the following String array for the rightmost occurrence of the word "hat". String [] words = { "cat", "hat", "mat", "bat", "hat", "sat" }; Your code must use the method declaration shown below. If the search key is found the method should return its array index. If the search key is not found the method should return the value 1. public static int rightmostSearch(String arrayll, String searchKey) cat hat mat bat hat sat Rightmost hat found at index 4. Question 2 Modify the Binary Search template code on MOODLE to calculate the average number of steps taken when searching a sorted data set that contains 250 random integer values (between 0 - 765). Your calculated average should be approximately the same as the theoretical average binary search time for a data set of size 250. O(log2(250))=7.96 Deliverables Place all your Java source files in a folder called Week4. Zip the Week4 folder and upload the zip file using the Week4 upload link for your group on MOODLE. All work must be submitted during your scheduled practical sessions