If you have created the contents of a collection, you probably know what is in it and what is not. But if the collection is prepared by another part of a large application, or even if you’ve just been putting objects into it and now need to find out if a given value was found, this recipe’s for you. There is quite a variety of methods, depending on which class of collection you have. The following methods can be used:
Method |
Meaning |
Implementing classes |
---|---|---|
|
Fairly fast search |
|
Linear search |
| |
Checks if the collection contains the object as a
|
| |
Returns location where object is found |
| |
Linear search |
|
This example plays a little game of “find the hidden
number” (or “needle in a haystack”); the numbers to
look through are stored in an array. As games go, it’s fairly
pathetic: the computer plays against itself, so you probably know
who’s going to win. I wrote it that way so I would know that
the data array contains valid numbers. The interesting part is not
the generation of the random numbers (discussed in Section 5.13). The array to be used with
Arrays.binarySearch( )
must be in sorted order, but since we
just filled it with random numbers, it isn’t initially sorted.
Hence we call Arrays.sort( )
on the array. Then we are in a position
to call Arrays.binarySearch( )
, passing in the
array and the value to look for. If you run the program with a
number, it runs that many games and reports on how it fared overall.
If you don’t bother, it plays only
one game.
import java.util.*; /** Array Hunt "game" (pathetic: computer plays itself). */ public class ArrayHunt { protected final static int MAX = 4000; // how many random ints protected final static int NEEDLE = 1999; // value to look for int haystack[]; Random r; public static void main(String argv[]) { ArrayHunt h = new ArrayHunt( ); if (argv.length == 0) h.play( ); else { int won = 0; int games = Integer.parseInt(argv[0]); for (int i=0; i<games; i++) if (h.play( )) ++won; System.out.println("Computer won " + won + " out of " + games + "."); } } /** Construct the hunting ground */ public ArrayHunt( ) { haystack = new int[MAX]; r = new Random( ); } /** Play one game. */ public boolean play( ) { int i; // Fill the array with random data (hay?) for (i=0; i<MAX; i++) { haystack[i] = (int)(r.nextFloat( ) * MAX); } // Precondition for binarySearch( ) is that array be sorted! Arrays.sort(haystack); // Look for needle in haystack. :-) i = Arrays.binarySearch(haystack, NEEDLE); if (i >= 0) { // found it - hurray, we win! System.out.println("Value " + NEEDLE + " occurs at haystack[" + i + "]"); return true; } else { // not found, we lose. System.out.println("Value " + NEEDLE + " does not occur in haystack; nearest value is " + haystack[-(i+2)] + " (found at " + -(i+2) + ")"); return false; } } }
Note that the Collections.binarySearch( )
works almost exactly the same way,
except it looks in a Collection
, which must be
sorted (presumably using Collections.sort
, as
discussed in Section 7.9).
52.15.78.83