Polymorphism - Java Software Solutions: Foundations of Program Design - page 515

LISTING 10.11 continued

System.out.println ("The contact was not found.");
System.out.println ();

Sorting.selectionSort(friends);

test = new Contact ("Mario", "Guzman", "");
found = (Contact) Searching.binarySearch(friends, test);
if (found != null )
System.out.println ("Found: " + found);
else
System.out.println ("The contact was not found.");
}
}

OUTPUT

Found: Phelps, Frank 322-555-2284

Found: Guzman, Mario 804-555-9066

Listing 10.12 shows the Searching class. It contains two static searching
algorithms.
In the linearSearch method, the while loop steps through the elements of
the array, terminating either when the target is found or the end of the array is
reached. The boolean variable found is initialized to false and is only changed to
true if the target element is located.
Note that we'll have to examine every element before we can conclude that the
target doesn't exist in the array. On average, the linear search approach will look
through half the data before finding a target that is present in the array.
The linearSearch method is implemented to process an array of Comparable
objects. For this algorithm, however, which relies only on the equals method,
that restriction is not necessary.

Binary Search
If the elements in an array are sorted, in either ascending or descending order,
then our approach to searching can be much more efficient than the linear search
algorithm. A binary search eliminates large parts of the search pool with each
comparison by capitalizing on the fact that the search pool is ordered.