public class BinaryArray
1: // Fig 16.4: BinaryArray.java
2: // Class that contains an array of random integers and a method
3: // that uses binary search to find an integer.
4: import java.util.Random;
5: import java.util.Arrays;
6:
7: public class BinaryArray
8: {
9: private int[] data; // array of values
10: private static Random generator = new Random();
11:
12: // create array of given size and fill with random integers
13: public BinaryArray( int size )
14: {
15: data = new int[ size ]; // create space for array
16:
17: // fill array with random ints in range 10-99
18: for ( int i = 0; i < size; i++ )
19: data[ i ] = 10 + generator.nextInt( 90 );
20:
21: Arrays.sort( data );
22: } // end BinaryArray constructor
23:
24: // perform a binary search on the data
25: public int binarySearch( int searchElement )
26: {
27: int low = 0; // low end of the search area
28: int high = data.length - 1; // high end of the search area
29: int middle = ( low + high + 1 ) / 2; // middle element
30: int location = -1; // return value; -1 if not found
31:
32: do // loop to search for element
33: {
34: // print remaining elements of array
35: System.out.print( remainingElements( low, high ) );
36:
37: // output spaces for alignment
38: for ( int i = 0; i < middle; i++ )
39: System.out.print( " " );
40: System.out.println( " * " ); // indicate current middle
41:
42: // if the element is found at the middle
43: if ( searchElement == data[ middle ] )
44: location = middle; // location is the current middle
45:
46: // middle element is too high
47: else if ( searchElement < data[ middle ] )
48: high = middle - 1; // eliminate the higher half
49: else // middle element is too low
50: low = middle + 1; // eliminate the lower half
51:
52: middle = ( low + high + 1 ) / 2; // recalculate the middle
53: } while ( ( low <= high ) && ( location == -1 ) );
54:
55: return location; // return location of search key
56: } // end method binarySearch
57:
58: // method to output certain values in array
59: public String remainingElements( int low, int high )
60: {
61: StringBuffer temporary = new StringBuffer();
62:
63: // output spaces for alignment
64: for ( int i = 0; i < low; i++ )
65: temporary.append( " " );
66:
67: // output elements left in array
68: for ( int i = low; i <= high; i++ )
69: temporary.append( data[ i ] + " " );
70:
71: temporary.append( "\n" );
72: return temporary.toString();
73: } // end method remainingElements
74:
75: // method to output values in array
76: public String toString()
77: {
78: return remainingElements( 0, data.length - 1 );
79: } // end method toString
80: } // end class BinaryArray
81:
82:
83: /**************************************************************************
84: * (C) Copyright 1992-2005 by Deitel & Associates, Inc. and *
85: * Pearson Education, Inc. All Rights Reserved. *
86: * *
87: * DISCLAIMER: The authors and publisher of this book have used their *
88: * best efforts in preparing the book. These efforts include the *
89: * development, research, and testing of the theories and programs *
90: * to determine their effectiveness. The authors and publisher make *
91: * no warranty of any kind, expressed or implied, with regard to these *
92: * programs or to the documentation contained in these books. The authors *
93: * and publisher shall not be liable in any event for incidental or *
94: * consequential damages in connection with, or arising out of, the *
95: * furnishing, performance, or use of these programs. *
96: *************************************************************************/