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

**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 0, 1, 2, 3, ..., n - 1, n, 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.