**Objective:** The goal of this assignment is to compare the
efficiency of different approaches to one specific problem:
search in a list of strings.

**Assignment.** Write the following three methods:

- First, assume that the list is given as an un-sorted array. In this case, we need to use linear search to find an element in this list.
- Second, assume that the list is given as a sorted array. In this case, we can use binary search.
- Third, assume that the list is given as a linked list. In this case, we also need to use linear search.

- call this method before running your method and record the value;
- then run your method;
- when the method finishes running, call System.currentTimeMillis() again to get the current time.

To test our methods, let us use a list consisting of squares
0^{2}=0, 1^{2}=1, 2^{2}=4, ..., (n
− 1)^{2}, and let us search for a randomly
selected element in this list (use the Java random number
generator to select a random integer i from 0 to n − 1,
and search for the value i^{2}). Run your program and
compare the times taken by the three methods for n = 1,000, n =
1,500, and n = 2,500. Record your observations and be able to
explain what is happening to your TA when you demo your
program.