**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 elements 1000, 1001, 1002, 1003, ..., 1000 + n - 1 (viewed as strings), and let us search for a randomly selected element in this list (use random number generator to select the element). Run your program and compare the times taken by the three methods for n = 500, n = 1,000, and n = 2,000. Record your observations and be able to explain what is happening to your TA when you demo your program.

*Hint.* To assign to the i-th element s[i] of a string array s
a value corresponding to the integer 1000 + i, we can use the code
s[i] = Integer.toString(1000 + i); a random element of this array is
just an element corresponding to a randomly selected index i.