Introduction to Objects - Advanced Topics in Java: Core Concepts in Data Structures - page 55

The main method sets up an array called person with data for seven people. It then requests the user to enter
names. For each name, sequentialSearch is called; it returns a value n , say. If found ( n >= 0 ), the age and gender of
the person is printed. If not, the message Not found is printed. The following is a sample run:
Enter names, one at a time, and I'll tell you
their age and gender. To end, press Enter
Olga
36 F
Bart
Not found
bert
32 M
INGA
21 F
Note how we define the class Person . We omit the word public so we can put it in the same file as SearchTest .
For variety, we use no access modifier ( public or private ) on the field names— name , age , gender . When we do this,
other classes in the same file can refer to the field names directly; for example, in main , we refer to person[n].age and
person[n].gender .
We can also use a binary search on an array of objects, provided the objects are sorted based on the field we want
to search. For example, we can binary-search the person array for a name provided the objects are arranged in order
by name. Here is the function:
// search for a person with name key in the first n elements of the
// array person ; if found, return the position, else return -1
public static int binarySearch(String key, Person[] person, int n) {
int lo = 0, hi = n - 1;
while (lo <= hi) { // as long as more elements remain to consider
int mid = (lo + hi) / 2;
int cmp = key.compareToIgnoreCase(person[mid].name);
if (cmp == 0) return mid; // search succeeds
if (cmp < 0) hi = mid - 1; // key is 'less than' person[mid].name
else lo = mid + 1; // key is 'greater than' person[mid].name
}
return -1; // key is not in the array
} // end binarySearch
As an exercise, write a program similar to Program P2.3 to test binarySearch .
2.13 Sorting an Array of Objects
We assume you know how to sort an array of strings or primitive types using selection and insertion sort.
The following shows how to sort an object array, Person , in ascending order by name using selection sort:
public static void selectionSort(Person[] list, int lo, int hi) {
// sort list[lo] to list[hi] using selection sort
for (int h = lo; h <= hi; h++)