Java Reference
In-Depth Information
4.
public static
<T>
boolean
contains(AList<T> theList, T anEntry)
{
return
search(theList, 1, theList.getLength(), anEntry);
}
// end contains
private static
<T>
boolean
search(AList<T> theList,
int
first,
int
last,
T desiredItem)
{
boolean
found;
if
(first > last)
found =
false
;
else if
(desiredItem.equals(theList.getEntry(first)))
found =
true
;
else
found = search(theList, first + 1, last, desiredItem);
return
found;
}
// end search
5.
Searching for 8 requires seven comparisons, as follows:
8 == 10?
8 < 10?
8 == 5?
8 < 5?
8 == 7?
8 < 7?
8 == 8?
Searching for 16 requires eight comparisons, as follows:
16 == 10?
16 < 10?
16 == 18?
16 < 18?
16 == 12?
16 < 12?
16 == 15?
16 < 15?
6.
a.
12 and 4.
b.
12, 4, and 8.
c.
12, 20, and 14.
7.
public int
contains(T anEntry)
{
return
binarySearch(0, numberOfEntries - 1, anEntry);
}
// end contains
private int
binarySearch(
int
first,
int
last, T desiredItem)
{
int
result;
int
mid = first + (last - first) / 2;
if
(first > last)
result = -1;
else if
(desiredItem.equals(list[mid]))
result = mid;
else if
(desiredItem.compareTo(list[mid]) < 0)
