Question

There are wide applications of the searching algorithm, where given a list of objects, to find whether the search target is in the list.

The intuitive solution is that we walk through the list until the search target is found or the end of the list is reached. The solution is called Linear Search.

For general purpose, let us use ListADT and define a static generic linear search method as follows:

public static <T extends Comparable<T>> int search(ListADT<T> array, T targetValue) throws EmptyCollectionException;

Please implement the linear search method, which walks through the given list and search for the targetValue until the targetValue is found or the end of the list is reached. If the targetValue is found, the method returns the index of the targetValue in the list or else it returns -1.

public static <T extends Comparable<T>> int search(ListADT<T> array, T targetValue) throws EmptyCollectionException {

}

In the hands-out or your sketchbook, please write down your code and take a snapshot and submit it.

Additionally, discuss and answer the following question:

what are the worst and average case running times for serial search?

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Note: Worst case running time of linear search is O(n) if n is the size of ListADT and the element to search is found at last index or not found. Best case running time is O(1) if element is found at index 0. If the elements are uniformly distributed, average running time will be O(n/2)

/**

* Since you did not provide ListADT or its methods, I'm writing this

* solution based on assumptions, assuming ListADT has methods get(index)

* that returns an element at a given index and size() that returns the

* number of elements.

*/

public static <T extends Comparable<T>> int search(ListADT<T> array,

            T targetValue) throws EmptyCollectionException {

      // looping from i=0 to i=array.size()-1

      for (int i = 0; i < array.size(); i++) {

            // getting element at i and comparing with targetValue

            if (array.get(i).equals(targetValue)) {

                  // found, returning index

                  return i;

            }

      }

      // not found, returning -1

      return -1;

}