SearchDemo.java

Download SearchDemo.java

  1: // This code shows the algorithms for linear and binary searching.
  2: // Note the Java Collections (in java.util package) contain various
  3: // collections and algorithms.
  4: //
  5: // Written 2003 by Wayne Pollock, Tampa Florida USA.
  6: 
  7: import java.util.Arrays;
  8: import javax.swing.JOptionPane;
  9: 
 10: public class SearchDemo
 11: {
 12:    public static void main ( String [] args )
 13:    {
 14:       Item [] list = {
 15:          new Item( 44, "Fifth" ),  new Item( 55, "Sixth" ),
 16:          new Item( 12, "Second" ),  new Item( 42, "Fourth" ),
 17:          new Item( 94, "Eighth" ),  new Item( 18, "Third" ),
 18:          new Item( 10, "First" ),  new Item( 67, "Seventh" ),
 19:       };
 20: 
 21:       System.out.println( "  Initial list:\n" );
 22:       dump( list );
 23: 
 24:       String input = JOptionPane.showInputDialog(
 25:          "Enter key value to search for: " );
 26: 
 27:       if ( input == null )
 28:          System.exit( 1 );
 29: 
 30:       int key = Integer.parseInt( input );
 31: 
 32:       Item item = linearSearch( key, list );
 33:       if ( item == null )
 34:          System.out.println( "\nNo item found with key " + key + "!\n" );
 35:       else
 36:          System.out.println( "\nFound item, key = " + item.key
 37:             + ", data = \"" + item.data + "\"" );
 38: 
 39:       System.out.println( "\n  Sorted list:\n" );
 40:       Arrays.sort( list );
 41:       dump( list );
 42:       item = binarySearch( key, list );
 43:       if ( item == null )
 44:          System.out.println( "\nNo item found with key " + key + "!\n" );
 45:       else
 46:          System.out.println( "\nFound item, key = " + item.key
 47:             + ", data = \"" + item.data + "\"" );
 48: 
 49:       System.exit( 0 );
 50:    }
 51: 
 52:    public static void dump ( Item [] list )
 53:    {
 54:       for ( int i = 0; i < list.length; ++i )
 55:          System.out.println( list[i].key + "\t" + list[i].data );
 56:       System.out.println();
 57:    }
 58: 
 59:    public static Item linearSearch ( int key, Item [] list )
 60:    {
 61:       for ( int i = 0; i < list.length; ++i )
 62:       {
 63:          if ( list[i].key == key )
 64:             return list[i];
 65: 
 66:          System.out.print( "checking " + list[i].key + "..." );
 67:       }
 68: 
 69:       return null;
 70:    }
 71: 
 72:    public static Item binarySearch ( int key, Item [] list )
 73:    {
 74:       int low = 0, high = list.length-1;
 75: 
 76:       while ( low <= high )
 77:       {
 78:          int mid = low + (high - low) / 2; // Note "(low+high)/2" can overflow.
 79:          //  Another way that works:  int mid = (low + high) >>> 1;
 80: 
 81:          if ( key == list[mid].key )
 82:             return list[mid];              /* found it! */
 83:          else if ( key < list[mid].key )
 84:             high = mid - 1;
 85:          else
 86:             low = mid + 1;
 87: 
 88:          System.out.print( "checking " + list[mid].key + "..." );
 89:       }
 90: 
 91:       return null;                         /* key not found. */
 92: 
 93:    }
 94: }
 95: 
 96: 
 97: class Item implements Comparable
 98: {
 99:    int key;
100:    String data;
101: 
102:    public Item ( int key, String data )
103:    {  this.key = key;
104:       this.data = data;
105:    }
106: 
107:    public int compareTo ( Object obj )
108:    {
109:       Item item = (Item) obj;
110:       // Since all keys are small positive integers just return the difference:
111:       return key - item.key;
112:    }
113: 
114:    public boolean equals ( Object obj )
115:    {
116:       return compareTo( obj ) == 0;
117:    }
118: }