/home/wpollock1/public_html/Java/SearchDemo.java

// This code shows the algorithms for linear and binary searching.
// Note the Java Collections (in java.util package) contain various
// collections and algorithms.
//
// Written 2003 by Wayne Pollock, Tampa Florida USA.

import java.util.Arrays;
import javax.swing.JOptionPane;

public class SearchDemo
{
   public static void main ( String [] args )
   {
      Item [] list = {
         new Item( 44, "Fifth" ),  new Item( 55, "Sixth" ),
         new Item( 12, "Second" ),  new Item( 42, "Fourth" ),
         new Item( 94, "Eighth" ),  new Item( 18, "Third" ),
         new Item( 10, "First" ),  new Item( 67, "Seventh" ),
      };

      System.out.println( "  Initial list:\n" );
      dump( list );

      String input = JOptionPane.showInputDialog(
         "Enter key value to search for: " );

      if ( input == null )
         System.exit( 1 );

      int key = Integer.parseInt( input );

      Item item = linearSearch( key, list );
      if ( item == null )
         System.out.println( "\nNo item found with key " + key + "!\n" );
      else
         System.out.println( "\nFound item, key = " + item.key
            + ", data = \"" + item.data + "\"" );

      System.out.println( "\n  Sorted list:\n" );
      Arrays.sort( list );
      dump( list );
      item = binarySearch( key, list );
      if ( item == null )
         System.out.println( "\nNo item found with key " + key + "!\n" );
      else
         System.out.println( "\nFound item, key = " + item.key
            + ", data = \"" + item.data + "\"" );

      System.exit( 0 );
   }

   public static void dump ( Item [] list )
   {
      for ( int i = 0; i < list.length; ++i )
         System.out.println( list[i].key + "\t" + list[i].data );
      System.out.println();
   }

   public static Item linearSearch ( int key, Item [] list )
   {
      for ( int i = 0; i < list.length; ++i )
      {
         if ( list[i].key == key )
            return list[i];

         System.out.print( "checking " + list[i].key + "..." );
      }

      return null;
   }

   public static Item binarySearch ( int key, Item [] list )
   {
      int low = 0, high = list.length-1;

      while ( low <= high )
      {
         int mid = low + (high - low) / 2; // Note "(low+high)/2" can overflow.
         //  Another way that works:  int mid = (low + high) >>> 1;

         if ( key == list[mid].key )
            return list[mid];              /* found it! */
         else if ( key < list[mid].key )
            high = mid - 1;
         else
            low = mid + 1;

         System.out.print( "checking " + list[mid].key + "..." );
      }

      return null;                         /* key not found. */

   }
}


class Item implements Comparable
{
   int key;
   String data;

   public Item ( int key, String data )
   {  this.key = key;
      this.data = data;
   }

   public int compareTo ( Object obj )
   {
      Item item = (Item) obj;
      // Since all keys are small positive integers just return the difference:
      return key - item.key;
   }

   public boolean equals ( Object obj )
   {
      return compareTo( obj ) == 0;
   }
}