©2010 Felleisen, Proulx, et. al.
Practice problems help you get started, if some of the lab and lecture
material is not clear. You are not required to do these problems, but
make sure you understand how you would solve them. Solving them on
paper is a great preparation for the exams.
Finish Lab 8 and include all the work in your portfolio.
Start with a new project and create two files: Algorithms.java
In the ExamplesAlgorithms make examples of sorted ArrayLists of Strings and Integers.
Of course, there is no constructor that creates an ArrayList filled with values. You need to define a method initData that adds the values to the initially empty ArrayLists one at a time.
Next, design two classes that implement the Comparator interface in Java Collections — one that compares Strings by lexicographical ordering, one that compares Integers by their magnitude.
Now, design the method binarySearch in the class Algorithms that consumes the lower index (inclusive), the upper index (exclusive), an ArrayList of data of the type T, a Comparator of the type T, and an object of the type T and produces the index for this object in the given ArrayList or throws a RuntimeException if the object is not found.