public class SortSearch {
  
  public static boolean linearSearch( int[] input, int item ) {
    int n = input.length;
    for( int i = 0; i < n; i++ ) {
        if( item == input[ i ] )        return true;
        if( item <  input[ i ] )        return false;
    }
    return false;
  }
  
  public static boolean binarySearch( int[] input, int item, 
                                      int first, int last ) {
    if( first == last )          // size 1 array
        return( item == input[ first ] );
    int pivot = input[ (first + last + 1)/2 ];
    if( item < pivot )
        return binarySearch( input, item, first, (first+last)/2 );
    else
        return binarySearch( input, item, (first+last+1)/2, last );
  }

  public static int[] insertionSort( int[] input ) {
    int   n            = input.length;
    int   sortedLength = 0;
    int[] sorted       = new int[ n ];

    for( int i = 0; i < n; i++ ) {
        int item = input[ i ];
        if( sortedLength == 0 ) {    // insert here
            sorted[ sortedLength++ ] = item;
        }  
        else {   // insert item into its proper place                        
            int j = 0;
            // find the item's place
            while( ( j < sortedLength ) && ( item >= sorted[ j ] ) )  
                j++;     
            int k = j;
            int temp = sorted[ k ];
            while( k < sortedLength ) {      // bump all remaining elements
                int temp2 = sorted[ k+1 ];   // back one position to make
                sorted[ k + 1 ] = temp;      // room for the element we want
                temp = temp2;                // to add
                k++;
            }
            sorted[ j ] = item;
            sortedLength++;
        }
    }
    return sorted;
  }
  
}