It is possible to enhance the efficiency of find operations on a list by using binary search. However, this requires restricting access to the location of data in the structure in order to maintain a sorted order.
The file SortedArray.java
contains the outline of an array based implementation of a sorted
list. Notice that the generic type for the class extends
Comparable. This means that only classes that implements Comparable
can be used as the generic type for the SortedList class. This is
necessary because it is not possible to sort objects unless they
can be compared. There is also an
ArrayList.java instance variable that
stores the objects in the list in ascending order. The
constructors and the toString methods are already
completed, however, you must complete each of the following
methods:
binarySearch method should return the index
of the first occurrence of the specified object. If the object
is not in the list, it should return where it would be added to
the list. You can use the constructor that takes an array list
of objects to test this method. Test thoroughly before
proceeding. The following three methods should all use
the binarySearch method.add method should add the specified object
to the sorted list, such that the list maintains its ascending
order. If the object is null, it should throw an exception.
Test thoroughly before proceeding.get method should return the first object
in the sorted list that is equivalent (according to the
compareTo method) to the specified object. If
there is no equivalent object in the list, it should return
null. Thoroughly test before proceeding.iterator method should return a new
SortedListIterator that begins iterating over the sorted list at
the first occurrence of an object equivalent to or greater than
the specified object. Test thoroughly before submitting.Submit a zip file of your code on the course Inquire site that uses your last names as the file name.