Search

Search Interface

• Create a package edu.emory.mathcs.cs323.search.
• Create an interface ISearch under search.
• Make a generic type T extendsComparable<T>.
• Declare an abstract method search.
• @param list a list containing zero to many keys.
• @param key a key to be searched.
• @return the index of the key in the list if exists; otherwise, a negative integer.

Linear and Binary Search

• Create classes LinearSearch and BinarySearch under search.
• Implement ISearch.
• Make a generic type T extends[Comparable<T>].
• Override the search method in each class for linear and binary search.
• For binary search, assume that the input list is sorted in ascending order.

Evaluation

• Assess LinearSearch and BinarySearch using:
• SearchTest#testAccuracy().
• Compare the speeds of LinearSearch and BinarySearch using:
• SearchTest#compareSpeed().

Exercise

• Imagine that the following condition didn't exist in BinarySearch (lines 45-46).

  if (beginIndex > endIndex)
    return -1;
  

• Give a list of integers containing more than one key, sorted in ascending order, that would make BinarySearch throw an exception or an error. Explain why this would be thrown.