Recipe 7.11 Finding an Object in a Collection

Problem

You need to see whether a given collection contains a particular value.

Solution

Ask the collection if it contains an object of the given value.

Discussion

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 collection class you have. The following methods can be used:

Method(s)	Meaning	Implementing classes
binarySearch( )	Fairly fast search	Arrays, Collections
contains( )	Linear search	ArrayList , HashSet, Hashtable, LinkList , Properties, Vector
containsKey( ), containsValue( )	Checks if the collection contains the object as a Key or as a Value	HashMap , Hashtable, Properties, TreeMap
indexOf( )	Returns location where object is found	ArrayList , LinkedList , List , Stack , Vector
search( )	Linear search	Stack

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 Recipe Recipe 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;         }     } }

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 Recipe 7.8).