public class Search
{
	//
    // Precondition: 	provide array[] an array of integers
    //                  size the number of integers in the array
    //					value the value to search for in the array
    // Postcondition: 	returns index of location of value in array using linear
    //                  search technique.  -1 is returned if array value is not found
    //
    public static int linearSearch(final int array[], int size, int value)
    {
        // Start at the beginning of the array.  Move left to right
        // through the array.  If value is encountered, then return
        // the index of value in the array.
        for (int index=0; index<size; index++) 
        {
            smallDelay();
            if (array[index]==value) 
            {
                return index;
            }
        }

        // If we searched the array, but did not find the value, then
        // return -1 indicating that the value is not in the array.
        return -1;
    }

	//
    // Precondition: 	provide array[] a SORTED array of integers
    //                  size the number of integers in the array
    //					value the value to search for in the array
    // Postcondition: 	returns index of location of value in array using binary
    //                  search technique.  -1 is returned if array value is not found
    //
    public static int binarySearch(final int array[], int size, int value)
    {
        // lower bound index of the interval that may contain value
        int lower=0;

        // upper bound index of interval that may contain value
        int upper=size-1;

        // middle of interval
        int middle=0;

        // Search array using smaller and smaller index intervals until
        //    - the value is found
        //    - the interval is smaller than zero
        // Each iteration of the while loop, halve the interval
        while (lower <= upper) 
        {
            // The middle of the interval is halfway between the lower and
            // upper bounds of the interval.
            middle = (lower + upper) / 2;

            smallDelay();
            //cout << "Interval is: " << (upper-lower) << " lower: " << lower << " upper: " << upper 
            //     << " a[lower]= " << array[lower]
            //     << " a[upper]= " << array[upper] 
            //     << " a[middle]= " << array[middle]
            //     << " value= " << value << endl;


            // Return the array index if value found
            if (value == array[middle]) 
            {
                    return middle;
            }

            // If value is less than middle, then shift the upper bound
            // of the interval to the left.
            else if (value < array[middle]) 
            {
                    upper = middle -1;
            }

            // If value is greater than middle, then shift the lower bound
            // of the interval to the right.
            else if (value > array[middle]) 
            {
                    lower = middle + 1;
            }
        }

        // If we get here, then the array doesn't contain the value.
        // Return index of -1.
        return -1;
    }

    // Precondition: 	provide array[] an array of integers in any order
    //                  size the number of integers in the array
    // Postcondition: 	outputs contents of array to standard out
    public void displayArray(final int array[], int size)
    {
        for (int i=0; i<size; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }

    // Precondition: 	provide array[] an array of integers
    //                  size the number of integers in the array
    // Postcondition: 	array[] is populated with random integers between 0 and 100000
    public static void populateUnsortedArray(int array[], int size)
    {
        for (int i=0; i<size; i++)
        {
            array[i]= (int)(Math.random() * 1000000) + 1;
        }

    }

    // Precondition: 	provide array[] an array of integers
    //                  size the number of integers in the array
    // Postcondition: 	array[] is populated with an ordered set of integers between where each
    //                  integer differs randomly from its neighbor by no more than 10
    public static void populateSortedArray(int array[], int size)
    {
        for (int i = 0; i < size; i++)
        {
            if (i == 0)
                array[i] = (int)(random() * 100) + 1;
            else
                array[i] = (int)(random() * 100) + 1 + array[i - 1];
        }
    }

    // Precondition: 	NONE
    //                
    // Postcondition:	creates a delay using sleep
    public static void smallDelay()
    {
		Thread.sleep(100);
    }

	//Precondition: NONE
	//
	//Postcondition: returns time in milliseconds since computer was turned on
	public static long currentTimeMillis()
	{
		return System.currentTimeMillis();
	}

	//Precondition: NONE
	//
	//Postcondition: returns a random double between 0 and 1
	public static double random()
	{
		return Math.random();
	}

    public static void main(String[]args)
    {	
		    final int SIZE = 1;
			int score[] = new int [SIZE];

            // Use populateUnsortedArray for linearSearch
            populateUnsortedArray(score, SIZE);

            // Use populateSortedArray for binarySearch
            //populateSortedArray(score,SIZE);

            long sum = 0;
            System.out.println("Performing search test...");
            for (int i=0; i<100; i++)
            {
                    long start = currentTimeMillis();
                    int value = (int)(random() * SIZE) + 1;

                    // Uncomment this for linear search
                    linearSearch(score,SIZE,value);

                    // Uncomment this for binary search
                    //binarySearch(score,SIZE,value);

                    long stop = currentTimeMillis();
                    sum = sum + stop-start;
            }

            System.out.println("Search array of size " + size + " took " + sum + " ms");
    }
}