Dictionary Implementations - Data Structures and Abstractions with Java - page 502

Using these methods, we can implement the method add as follows:

public V add(K key, V value)
{

V result = null ;
int keyIndex = locateIndex(key);

if ( (keyIndex < numberOfEntries) &&
key.equals(dictionary[keyIndex].getKey()) )

{

// key found; return and replace old value
result = dictionary[keyIndex].getValue();
dictionary[keyIndex].setValue(value);

}
else
{

ensureCapacity();
makeRoom(keyIndex);
dictionary[keyIndex] = new Entry<K, V>(key, value);
numberOfEntries++;
} // end if
return result;
} // end add

20.12

The method locateIndex . Since the array is sorted, locateIndex can generally search it in less
time than it could search an unsorted array. Recall from Segment 18.8 of Chapter 18 that a sequen-
tial search can detect when an entry is not in a sorted array without searching the entire array. Using
that technique, we define the private method locateIndex as follows:

private int locateIndex(K key)
{

// search until you either find an entry containing key or
// pass the point where it should be
int index = 0;
while ( (index < numberOfEntries) &&
key.compareTo(dictionary[index].getKey()) > 0 )
index++;
return index;
} // end locateIndex
The difference between this method and the one given in Segment 20.5 for an unsorted dictionary is
highlighted.

Question 3 A binary search would be faster, in general, than the modified sequential
search just given—particularly when the dictionary is large. Implement the private method
locateIndex for a sorted dictionary using a binary search.

20.13

Removing an entry. To remove an entry from a sorted array-based dictionary, we first locate the
entry by calling the method locateIndex that we used in the previous segment for the add
method. Since the entries are sorted, we must maintain their order. Thus, any entries after the
one to be removed must shift to the next lower position in the array. Figure 20-5 illustrates these
two steps.