/**
 * Matt Kretchmar
 * April 1, 2006
 * Searching.java
 * This program illustrates two basic searching algorithms: sequential 
 * search (on sorted and unsorted data) and binary search.
 */
import java.util.Scanner;

class Searching
{
    public static void main ( String args[] )
    {
        int array[] = { 3, 7, 11, 18, 24, 29, 33, 38 };
        int key;
        int spot;
        Scanner keyboard = new Scanner(System.in);
        
        System.out.println("Enter key to search for: ");
        key = keyboard.nextInt();
        
        spot = sequentialSearchUnsorted ( array, key );
        System.out.println("Sequential search (unsorted): " + spot);
        
        spot = sequentialSearchSorted ( array, key );
        System.out.println("Sequential search (sorted): " + spot);
        
        spot = binarySearch ( array, key );
        System.out.println("Binary search: " + spot);
        
        spot = binarySearchRecursive ( array, key, 0, array.length-1 );
        System.out.println("Binary search (recursive): " + spot);
    }

    /**
     * This method uses sequential search to look through an array of
     * unsorted data.  It returns the index of the key item or -1 if the
     * key is not found.
     */
    public static int sequentialSearchUnsorted ( int a[], int key )
    {
        for ( int i = 0; i < a.length; i++ )
        {
            if ( a[i] == key )
                return i;
        }
        return -1;
    }

    /**
     * This method uses sequential search to look through an array of
     * sorted data.  It returns the index of the key item or -1 if the
     * key is not found.
     */
    public static int sequentialSearchSorted ( int a[], int key )
    {
        for ( int i = 0; i < a.length; i++ )
        {
            if ( a[i] == key )
                return i;
            else if ( key < a[i] )
                return -1;
        }
        return -1;
    }
    
    /**
     * This method uses binary search to look through an array of
     * sorted data.  It returns the index of the key item or -1 if the
     * key is not found.
     */
    public static int binarySearch ( int a[], int key )
    {
        int start, end, mid;
        start = 0;
        end = a.length-1;
        while ( start <= end )
        {
            mid = (start + end)/2;
            if ( key == a[mid] )
                return mid;
            else if ( key < a[mid] )
                end = mid-1;
            else
                start = mid+1;
        }
        return -1;
    }
    
    /**
     * This method uses binary search to look through an array of
     * sorted data.  It returns the index of the key item or -1 if the
     * key is not found.  It is a recursive version of binary search.
     */
    public static int binarySearchRecursive ( int a[], int key, int startIndex, int endIndex )
    {
        if ( startIndex > endIndex )
            return -1;
        int mid = (startIndex + endIndex) / 2;
        if (  key == a[mid] ) 
            return mid;
        else if ( key < a[mid] )
            return binarySearchRecursive(a,key,startIndex,mid-1);
        else
            return binarySearchRecursive(a,key,mid+1,endIndex);
     }
}