import java.util.ArrayList;

class LinearSearch
{
    //-------------------------//
    // Iterative Linear Search //
    //-------------------------//
    public int iLinearSearch( ArrayList<Integer> list, int key )
    {
        for( int i = 0; i < list.size(); i++ ) {
            if( key == list.get(i) ) {
                return i;
            }
        }
        
        return -1;
    }
    
    //-------------------------//
    // Recursive Linear Search //
    //-------------------------//

    // Starter method - initialize index to 0
    public  int rLinearSearch( ArrayList<Integer> list, int key )
    {
        return rLinearSearch( list, key, 0 );
    }

    private  int rLinearSearch( ArrayList<Integer> list, int key, int index )
    {
        if( index == list.size() )      // Base case #1
            return -1;                  // not found

        if( key == list.get(index) )         // Base case #2
            return index;           // found

        return rLinearSearch( list, key, index + 1 ); // Recursive case
    }
    
    //----------------------------------//
    // Recursive Modified Linear Search //
    //----------------------------------//

    public int modifiedLinearSearch( ArrayList<Integer> list, int key )
    {
        if( list.size() == 0 ) {        // Base case#1
            return -1;                      // no more data to search
        }
        
        if( key == list.get(0) ) {      // Base case#2
            return 0;                          // found it
        }
        
        // Recursive case
        
         // use a new list to prevent overwriting the original list
        ArrayList<Integer> tmpList = new ArrayList<Integer>();
        tmpList.addAll(list);          // copy everything from the original
        tmpList.remove( 0 );        // remove the first element
        
        int count = modifiedLinearSearch( tmpList, key );
        
        if( count == -1 ) {         // it's returned from the end of the list (BC#1)
            return -1;                  // continue to pass on the -1 back
        }
        
        return 1 + count;         // If the key is found, increment the count.
    }
}