The basic operation look the item the middle the range

CHAPTER 7. ARRAYS 349

above contain values that are greater than or equal to 93. These locations can be eliminated as possible locations of the number 42.

// At this point, highestPossibleLoc < LowestPossibleLoc, // which means that N is known to be not in the array. Return // a -1 to indicate that N could not be found in the array.

return -1;

Association lists are very widely used in computer science. For example, a compiler has to keep track of the location in memory associated with each variable. It can do this with an association list in which each key is a variable name and the associated value is the address of that variable in memory. Another example would be a mailing list, if we think of it as

associating an address to each name on the list.

The data for a phone directory consists of an array of type PhoneEntry[ ] and an integer variable to keep track of how many entries are actually stored in the directory. The technique of “dynamic arrays” (Subsection 7.3.2) can be used in order to avoid putting an arbitrary limit on the number of entries that the phone directory can hold. Using an ArrayList would be another possibility. A PhoneDirectory class should include instance methods that implement the “get”and “put” operations. Here is one possible simple definition of the class:

/**
* A PhoneDirectory holds a list of names with a phone number for * each name. It is possible to find the number associated with * a given name, and to specify the phone number for a given name.

}

private PhoneEntry[] data; private int dataCount;