With java

3. Have a public static main(String args[]) method that starts with the following two lines: Scanner in = new Scanner(System.in); List myList = null; 4. Copy your myPopulateRandomly method from Lab1 into the Lab2 class. You'll need to use it to populate a List with randomly-generated ints. Follow the instructions in the Requirements section to see exactly what you have to do for this lab. Requirements: Do the following: 1. Implement a public static generic mySearch method that takes as its first parameter a List and as its second parameter a target element for which to search. The idea is that mySearch will return any index of target within the List, and 1 if target does not occur in the List. It may only use the List methods size (] and get(i). You'll need to have a nested loop structure. It should check the elements, using the .equals method, in the following order: In the first iteration of the outer loop, check the element at index 0 . In the next iteration, check the elements at index 0 and listSize / 2. Then, check the elements at index 0, listSize / 4, listSize / 2 and 3 listSize / 4. Continue searching in this fashion until you eventually check every fourth element in the third-to-last iteration of the outer loop, and then every other element in the second-to-last iteration of the outer loop and finally you check every element in the last iteration of the outer loop. If, for any element that you check, within any iteration, you find the target element, just return its index. 2. Instantiate a List and call it myList. It needs to point at some kind of concrete List, so choose carefully. In order to justify your choice of List in this step, give a comment near (above, below or on the same line as) the instantiation step for myList, giving the worst-case asymptotic running times, expressed using big- , of the respective get(i) operations for either type of List. 3. Do the following until the user types quit: (a) Prompt the user to enter and then read in an int, say num. (b) Populate myList with num randomly-generated ints. This is where you should use your (correct and efficient implementation of myPopulateRandomly from Lab1. (c) Print out the first, middle and last elements of myList. (d) Print out an int that is not in myList. (e) Prompt the user to enter and then read in a target element (for which to search). (f) Call mySearch five times, passing in the same parameters each time: myList and target. Compute the average execution time over all five calls. The reason we take the average execution time over five runs is because the first run might be really slow compared to the subsequent runs and then the subsequent ones might be faster because data gets cached, etc. Another reasonable approach would be to compute the average of several runs, but not counting the first run. (g) Print out the result of the search. Technically, you did five searches, but they should all give the same result. (h) Print out the average execution time computed in step 3f. 4. Your program should print out Done. Normal termination, before actually terminating. 5. Use the given Scanner for all input. 6. Mimic the sample output shown in the Sample output section. 7. Finally, use your testbed main to try and determine the best possible big-O for the worst-case asymptotic running time of mySearch. Be sure to put your answer in the comment block of mySearch, along with a corresponding justification. Recall from our discussion from class that saying "mySearch has worst-case asymptotic running time O(2N, while perhaps technically correct, is not very meaningful and therefore would not be the best possible big-O that you'll want to state. However, bottom line is that you need to give an asymptotic upper bound here that is at least correct. For the sake of simplicity, assume that calling .equals results in the execution of O(1) simple operations. Sample output: How many numbers do you want? 1000003 1501557569 is in the middle of list. 1365553008 is the first element of the list. 2015528966 is the last element of the list. 46300 is not in the list. For what number do you want to search? 1501557569 FOUND: 1501557569 is in the list at index=500001 Average execution time over 5 calls: 0ms. How many numbers do you want? 2000000 667085623 is in the middle of list. 1365553008 is the first element of the list. 809911619 is the last element of the list. 1132905 is not in the list. For what number do you want to search? 777 NOT FOUND: 777 is not in the list. Average execution time over 5 calls: 4ms. How many numbers do you want? 4000000 432901423 is in the middle of list. 1365553008 is the first element of the list. 734379507 is the last element of the list. 748824 is not in the list. For what number do you want to search? 777 NOT FOUND: 777 is not in the list. Average execution time over 5 calls: 11ms. How many numbers do you want? 8000001 1729464087 is in the middle of list. - 1365553008 is the first element of the list. -2058767653 is the last element of the list. 3562242 is not in the list. For what number do you want to search? 777 NOT FOUND: 777 is not in the list. Average execution time over 5 calls: 21ms. How many numbers do you want? quit Done. Normal termination