/**
 * @(#)Lab3.java
 *
 * Lab3 application
 *
 * @author
 * @version 1.00 2011/2/20
 */
import java.util.*;


public class Lab3 {

    public static void main(String[] args) {
    System.out.println("It took : " + SortedArray500() + " milliseconds to find the element in array size 500");
    System.out.println("It took : " + SortedArray1000() + " milliseconds to find the element in array size 1000");
    System.out.println("It took : " + SortedArray2000() + " milliseconds to find the element in array size 2000");
    System.out.println("It took : " + UnSorted500() + " milliseconds to find the element in UnSorted array size 500");

    }



    // SORTED METHODS BINARY SEARCH!!!!!
    public static long SortedArray500()
    {

        int [] SArray500 = new int [500]; // Create Array of 500
        int low = 0;
        int high = SArray500.length-1;
        int mid = (low+high)/2;
        boolean found = false;

        Random generator = new Random(); // Create Random number generator
        int r = generator.nextInt(500); // Random generator to create numbers from 0-499

        for (int i = 0; i < SArray500.length; i++)
            SArray500[i] = i;

        int i = generator.nextInt(500); // Random generator to create numbers from 0-499
        System.out.println("i =" + i);
        long beforeMethod = System.currentTimeMillis();
        while (!found)  // Search for random number if not found go on to next element.
        {
            if (mid == i)
            {
                found = true;
            }
            else if (i < mid)
            {
                high = mid;
                mid = (low + mid)/2;
            }
            else if (i > mid)
            {
                low = mid;
                mid = (mid+high)/2;
            }
            if (!found)
            {
                return -1;
            }
            else
            {
                return mid;
            }
        }
        long afterMethod = System.currentTimeMillis();
        return (afterMethod-beforeMethod);
    }
    public static long SortedArray1000()
    {

        int [] SArray1000 = new int [1000]; // Create Array of 1000
        Random generator = new Random(); // Create Random number generator
        int r = generator.nextInt(1000);    // Random generator to create numbers from 0-999

        for (int i = 0; i < SArray1000.length; i++)
        {
            SArray1000[i] = i;
        }

        int i = 0;  // Set i back to 0
        long beforeMethod = System.currentTimeMillis();
        while (SArray1000[i] != r)  // Search for random number if not found go on to next element.
        {
            i++;
        }
        long afterMethod = System.currentTimeMillis();
        return (afterMethod-beforeMethod);
    }
    public static long SortedArray2000()
    {
        int [] SArray2000 = new int [2000]; // Create Array of 2000
        Random generator = new Random(); // Create Random number generator
        int r = generator.nextInt(2000);    // Random generator to create numbers from 0-1999

        for (int i = 0; i < SArray2000.length; i++)
        {
            SArray2000[i] = i;
        }

        int i = 0;  // Set i back to 0
        long beforeMethod = System.currentTimeMillis();
        while (SArray2000[i] != r)  // Search for random number if not found go on to next element.
        {
            i++;
        }
        long afterMethod = System.currentTimeMillis();
        return (afterMethod-beforeMethod);
    }
    // UNSORTED METHODS

    public static long UnSorted500()
    {
        int[] sortedArray500 = new int [500]; // Create Array of 500
        int[] unsortedArray500 = new int[500];
        Random generator = new Random(); // Create Random number generator
        int r = generator.nextInt(500); // Random generator to create numbers from 0-499
        for (int i = 0; i < sortedArray500.length; i++)
            sortedArray500[i] = i;

        int k = 0;
            while(k < unsortedArray500.length)
            {
                    r = generator.nextInt(500);
                    if(sortedArray500[r] != -1)
                    {
                        unsortedArray500[k] = sortedArray500[r];
                        sortedArray500[r] = -1;
                        k++;
                    }
            }
        r = generator.nextInt(500);
        long beforeMethod = System.currentTimeMillis();
        int i = 0;
        while (unsortedArray500[i] != r)    // Search for random number if not found go on to next element.
        {
            i++;
        }
        long afterMethod = System.currentTimeMillis();
        return (afterMethod-beforeMethod);
    }
}