import java.lang.System;
import java.lang.Math;

public class searchTest {
    // this procedure provides timing data for linear and binary searches

    public static void main (String argv[]) {
        // declaration of variables
        SimpleInput in = new SimpleInput();
        SimpleOutput out = new SimpleOutput();

        int numTrials = 10;    // number of experiments per array size
        int numReps = 100000;   // number of times experiment completed
        int currentTrial; // number of current trial at given size
        int arraySize;    // size of current array
        int item;         // item to search for in array
        int i, j;         // index variables
        int lo, hi, mid;  // binary search variables
        long startTime, endTime; // variables to count milliseconds
        boolean result = false;  // conclusion of search

        out.println ("Program to provide timing data for search algorithms");
        out.print ("Enter size array to test: ");
        arraySize = in.readInt ();

        out.println ("Random values will be searched in array 0, 2, 4, ...");
        out.println ("A total of " + (2*numTrials) + " trials will be reported.");
        out.println ("   In " + numTrials + " trials, the search will be successful.");
        out.println ("   In " + numTrials + " trials, the search will be unsuccessful.");
        out.println ("Results are based on " + numReps 
                   + " repetitions of the experiment.");

        out.println ();
        out.println ("Results of experiments (all times in milliseconds)");
        out.println ("                   linear          binary");
        out.println ("trial              search          search");
        out.println ("number item     result time     result time");

        // setup array
        int[] a = new int [arraySize];
        for (i = 0; i<arraySize; i++)
            a[i] = 2*i;

        out.println();
        for (currentTrial = 1; currentTrial <= 2*numTrials; currentTrial++) {
            // conduct experiments

            out.print (currentTrial);

            // pick item to search for
            if (currentTrial < numTrials)
                 item = 2*(int)Math.floor((arraySize-1)*Math.random());
            else {
                item = (int)Math.floor(3*arraySize*Math.random()-(arraySize/2));
                if ((item >= 0) && (item%2 == 0))
                    item += 1;
            }
            out.print ("\t"+item);
            // record time and result for linear search
            startTime = System.currentTimeMillis();
            for (i = 0; i<numReps; i++) {
                // linear search algorithm
                j = 0;
                while (j < a.length && item != a[j])
                    j++;
                result = (j != a.length);
            }
            endTime = System.currentTimeMillis();
            out.print ("\t" + result);
            out.print ("\t" + (endTime-startTime));
            
            // record time and result for binary search
            startTime = System.currentTimeMillis();
            for (i = 0; i<numReps; i++) {
                // binary search algorithm
                lo = 0;
                hi = a.length;
                mid = (hi + lo)/2;
                result = false;
                while (!result && lo < hi) {
                    if (a[mid] == item)
                        result = true;
                    else if (a[mid] < item)
                        lo = mid + 1;
                    else hi = mid;
                    mid = (hi + lo)/2;
                }
            }
            endTime = System.currentTimeMillis();
            out.print ("\t" + result);
            out.println ("\t" + (endTime-startTime));
        }
    } // main
} // searchTest