By using Java

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.