/**
 * @(#)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() + " NanoSeconds to find the element in array size 500");
    System.out.println("It took : " + SortedArray1000() + " NanoSeconds to find the element in array size 1000");
    System.out.println("It took : " + SortedArray2000() + " NanoSeconds to find the element in array size 2000");
    System.out.println("It took : " + UnSorted500() + " NanoSeconds to find the element in UnSorted array size 500");
    System.out.println("It took : " + UnSorted1000() + " NanoSeconds to find the element in UnSorted array size 1000");
    System.out.println("It took : " + UnSorted2000() + " NanoSeconds to find the element in UnSorted array size 2000");
    }



    // 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
        long beforeMethod = System.nanoTime();
        while (!found)  // While loop for binary search
        {
            if (mid == i)
            {
                found = true;
            }
            if (i < mid)
            {
                high = mid;
                mid = (low + mid)/2;
            }
            if (i > mid)
            {
                low = mid;
                mid = (mid+high)/2;
            }
        }
        long afterMethod = System.nanoTime();
        return (afterMethod-beforeMethod);
    }
    public static long SortedArray1000()
    {
        int [] SArray1000 = new int [1000]; // Create Array of 1000
        boolean found = false;
        int low = 0;
        int high = SArray1000.length-1;
        int mid = (low+high)/2;
        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 = generator.nextInt(1000);    // Random generator to create numbers from 0-999
        long beforeMethod = System.nanoTime();
        while (!found)  // While loop for binary search
        {
            if (mid == i)
            {
                found = true;
            }
            if (i < mid)
            {
                high = mid;
                mid = (low + mid)/2;
            }
            if (i > mid)
            {
                low = mid;
                mid = (mid+high)/2;
            }
        }
        long afterMethod = System.nanoTime();
        return (afterMethod-beforeMethod);
    }
    public static long SortedArray2000()
    {
        int [] SArray2000 = new int [2000]; // Create Array of 2000
        boolean found = false;
        int low = 0;
        int high = SArray2000.length-1;
        int mid = (low+high)/2;
        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 = generator.nextInt(200); // Random generator to create numbers from 0-1999
        long beforeMethod = System.nanoTime();
        while (!found)  // While loop for binary search
        {
            if (mid == i)
            {
                found = true;
            }
            if (i < mid)
            {
                high = mid;
                mid = (low + mid)/2;
            }
            if (i > mid)
            {
                low = mid;
                mid = (mid+high)/2;
            }
        }
        long afterMethod = System.nanoTime();
        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.nanoTime();
        int i = 0;
        while (unsortedArray500[i] != r)    // Search for random number if not found go on to next element.
        {
            i++;
        }
        long afterMethod = System.nanoTime();
        return (afterMethod-beforeMethod);
    }
    public static long UnSorted1000()
    {
        int[] sortedArray1000 = new int [1000]; // Create Array of 1000
        int[] unsortedArray1000 = new int[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 < sortedArray1000.length; i++)
            sortedArray1000[i] = i;

        int k = 0;
            while(k < unsortedArray1000.length)
            {
                    r = generator.nextInt(1000);
                    if(sortedArray1000[r] != -1)
                    {
                        unsortedArray1000[k] = sortedArray1000[r];
                        sortedArray1000[r] = -1;
                        k++;
                    }
            }
        r = generator.nextInt(1000);
        long beforeMethod = System.nanoTime();
        int i = 0;
        while (unsortedArray1000[i] != r)   // Search for random number if not found go on to next element.
        {
            i++;
        }
        long afterMethod = System.nanoTime();
        return (afterMethod-beforeMethod);
    }
        // UNSORTED 2000
        public static long UnSorted2000()
    {
        int[] sortedArray2000 = new int [2000]; // Create Array of 2000
        int[] unsortedArray2000 = new int[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 < sortedArray2000.length; i++)
            sortedArray2000[i] = i;

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