Download Searches Java
1.
Download Searches.java; this file defines a Searches class providing versions of the
search algorithms linearSearch and binarySearch. Make sure
the Searches class compiles before continuing.
2. Make these algorithms generic, so that they will work on any object type. Using the
techniques described in Chapter 2, modify each method: change the types of the
parameters, and (if appropriate) local variables, to use the type specifier T for each
method.
Note: for static methods, Java requires us to add <T> after the keyword static. So for
example:
public static <T> boolean contains( …etc…)
3. Next, because we want to search for any kind of objects and not just ints, we have to be
careful about how we compare them (both for equality and greater than/less than). The
operators for primitive types will no longer work correctly. You know that every class
inherits or overrides the equals method from Object. This will work in place of the
== operator for the linear searches.
For other comparisons, as in binarySearch, take advantage of
the compareTo method provided by the Comparable interface. Use this method in
place of greater than/less than operators.
You can read up on this interface in the text, Chapter 5, page 314-315; the basic idea is
that we can compare any objects which implement the interface using the following
method:
public int compareTo(String anotherString) // this is the
version for the String class
This method returns the value 0 if the strings are equal; a value less than 0
if this string is lexicographically less than anotherString; and a value greater
than 0 if this string is lexicographically greater than anotherString.
Note that we will simply use this method and assume that it is defined for the types
used with our search methods. You do not have to implement your own!
4. Now we have three generic methods that will work on different types of objects. The
trouble is, if I call these methods with an array of objects that don’t
implement Comparable, this code will fail. We’d like to ensure that the type parameter
used by our generic methods “screens out” object types that aren’t searchable. We do that
by using this extended form of generics:
<T extends Comparable<? super T>>
What does all that mean? For our purposes, focus in on the first part: here, T is just the
type parameter and <T extends Comparable> constrains that type parameter to
be one that provides a compareTo method, thereby implementing
the Comparable interface. If you add this more complex form of type parameter,
things that can’t be compared won’t compile if someone tries to pass an array of a noncomparable
type.
5.
6. Write a short program SearchTest.java to test your methods with two different array
types. Do 2 successful searches and 2 unsuccessful searches with each method and print
the results. Use these array declarations:
Integer[] testInts = {-12, -7, -4, -2, 0, 3, 5, 9, 13,
18, 22, 45};
7. String[] buildings = {“All Saints”, “Breslin”, “duPont”,
“Fulford”, “Gailor”, “Guerry”, “McClurg”, “Spencer”,
“Woods”};