//********************************************************************
//  Searching.java       Author: Lewis/Loftus
//
//  Demonstrates the linear search and binary search algorithms.
//********************************************************************

public class Searching
{
   //-----------------------------------------------------------------
   //  Searches the specified array of objects for the target using
   //  a linear search. Returns a reference to the target object from
   //  the array if found, and null otherwise.
   //-----------------------------------------------------------------
   public static Comparable linearSearch (Comparable[] list,
                                          Comparable target)
   {
      int index = 0;
      boolean found = false;

      while (!found && index < list.length)
      {
         if (list[index].equals(target))
            found = true;
         else
            index++;
      }

      if (found)
         return list[index];
      else
         return null;
   }

   //-----------------------------------------------------------------
   //  Searches the specified array of objects for the target using
   //  a binary search. Assumes the array is already sorted in
   //  ascending order when it is passed in. Returns a reference to
   //  the target object from the array if found, and null otherwise.
   //-----------------------------------------------------------------
   public static Comparable binarySearch (Comparable[] list,
                                          Comparable target)
   {
      int min=0, max=list.length, mid=0;
      boolean found = false;

      while (!found && min <= max)
      {
         mid = (min+max) / 2;
         if (list[mid].equals(target))
            found = true;
         else
            if (target.compareTo(list[mid]) < 0)
               max = mid-1;
            else
               min = mid+1;
      }

      if (found)
         return list[mid];
      else
         return null;
   }
}