I stock on how to call the method to initialize the list and so on achieve the requirements
I put requirements inside the comments of code.
Code
/* 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*/ public class Lab2 { public static void main(String args[]) { Scanner in = new Scanner(System.in); List myList = null; Random rand = new Random(); System.out.println("Populated array is:"); int howMany = in.nextInt(); List myList = new ArrayList(); myList(myPopulateRandomly(ArrayList inList,int howMany); } /*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). Youll 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. If you get through all iterations without finding the target element, then return -1. Correctness of the search algorithm follows from the fact that, in the last iteration of the outer loop, you check every element of the List*/ public static int mySearch(List myList, int target){ for(int i=0;i inList,int howMany){ Random a = new Random(); for (int i = 0; i Sample out:
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: Oms. 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. 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: Oms. 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
