//********************************************************************
//  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;
    }
}