Search and Select

Select Abstract Class

• Create a package edu.emory.mathcs.cs323.select.
• Create an abstract class AbstractSelect under select.
• Make a generic type T extendsComparable<T>.
• Declare an abstract method select.
• @param list a list of unsorted keys.
• @param k the k'th maximum key to search.
• @return the k'th maximum key in the list.
• @throwsIllegalArgumentException if the size of the list is smaller than k.

Dumb Select

• Create a class DumbSelect under select.
• Extend AbstractSelect.
• Make a generic type T extends[Comparable<T>]
• Override the select method in the class.
• Make a copy of the input list.
• Find and remove the maximum key from the copied list.
• Repeat this procedure k times, and return the last maximum key.

Smart Select

• Create a class SmartSelect under select.
• Extend AbstractSelect.
• Make a generic type T extends[Comparable<T>]
• Override the select method in the class.
• Create a new empty list, maxK.
• For each key in the input list,
  • Add the key to maxK.
  • If the size of maxK is greater than k, remove the minimum key in maxK.
• Return the minimum key in maxK.

Evaluation

• Assess LinearSearch and BinarySearch using:
• SearchTest#testAccuracy().
• Assess DumbSelect and SmartSelect using:
• SelectTest#testAccuracy().
• Compare the speeds of LinearSearch and BinarySearch using:
• SearchTest#compareSpeed().
• Compare the speeds of DumbSelect and SmartSelect using:
• SelectTest#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 a different kind of exception or error. Explain why this would be thrown.