//////////////////////////////
//Coded by. Avatar Fearless//
//Anti-armenia.ORG//////////
/////No More School!///////
//Special Thanks to LSS///
/////////////////////////
import java.util.*;
    public class SearchingMain extends Dice
    {
            static final int NOT_FOUND = -1;
            static long bTime;
            static long lTime;
            static long start;
     
            public SearchingMain()
            {
                    bTime = 0;
                    lTime = 0;
                    start = 0;
            }
     
            public static void main(String[] args)
            {
                    int num1 = 1;
                    final int CONSTANT = 1000;
                    final int FIRST = 0;
                    final int MIDDLE = 499;
                    final int LAST = 999;
                    final int DICESIZE = 1000000;
     
                    Dice roller = new Dice(DICESIZE);
                    Integer[] theArray = new Integer[CONSTANT];
     
                    for(int k = 0; k < 1000; k++)
                    {
                            //int num = roller.roll();
                            //theArray[k] = num;
                            theArray[k] = num1;
                            //System.out.println(num1);
                            num1++;
                    }
     
                    //System.out.println("First Value: " + theArray[FIRST] + " has an index of " + FIRST);
                    //System.out.println("Middle Value: " + theArray[MIDDLE] + " has an index of " + MIDDLE);
                    //System.out.println("Last Value: " + theArray[LAST] + " has an index of " + LAST);
     
                    System.out.println("Searching for first value... " + theArray[FIRST] + ", the first value is stored at index location " + linearSearch(theArray, new Integer(theArray[FIRST])));
                    System.out.println("Searching for middle value... " + theArray[(CONSTANT / 2) - 1] + ", the middle value is stored at index location " + linearSearch(theArray, new Integer(theArray[(CONSTANT / 2) - 1])));
                    System.out.println("Searching for last value... " + theArray[CONSTANT - 1] + ", the first last is stored at index location " + linearSearch(theArray, new Integer(theArray[CONSTANT - 1])));
                    System.out.println("Searching for value -1... returns " + linearSearch(theArray, new Integer(-1)));
                    System.out.println("Searching for value 100001... returns " + linearSearch(theArray, new Integer(100001)));
                    System.out.println("The linear search took " + lTime + " milliseconds.");
     
                    System.out.println("Searching for first value... " + theArray[FIRST] + ", the first value is stored at index location " + binarySearch(theArray, new Integer(theArray[FIRST])));
                    System.out.println("Searching for middle value... " + theArray[(CONSTANT / 2) - 1] + ", the middle value is stored at index location " + binarySearch(theArray, new Integer(theArray[(CONSTANT / 2) - 1])));
                    System.out.println("Searching for last value... " + theArray[CONSTANT - 1] + ", the first last is stored at index location " + binarySearch(theArray, new Integer(theArray[CONSTANT - 1])));
                    System.out.println("Searching for value -1... returns " + binarySearch(theArray, new Integer(-1)));
                    System.out.println("Searching for value 100001... returns " + binarySearch(theArray, new Integer(100001)));
                    System.out.println("The binary search took " + bTime + " milliseconds.");
     
            }
                    private static int linearSearch(Object[] list, Object x)
                    {
                            start = System.currentTimeMillis();
     
                            for(int k = 0; k < list.length; k++)
                            {
                                    if(list[k].equals(x))
                                            return k;
                            }
                            lTime = System.currentTimeMillis() - start;
                            return NOT_FOUND;
                    }
     
                    private static int binarySearch(Comparable[] list, Comparable x)
                    {
                            start = System.currentTimeMillis();
                            int low = 0;
                            int high = list.length - 1;
                            int mid;
     
     
                            while (low <= high)
                            {
     
                                    mid = (low + high) / 2;
                                    int check = list[mid].compareTo(x);
                                    if (check == 0)
                                    {
                                            bTime = System.currentTimeMillis() - start;
                                            return mid;
                                    }
     
     
                                    if (check < 0)
                                    low = mid + 1;
                                    else
                                            high = mid - 1;
                            }
                            bTime = System.currentTimeMillis() - start;
                            return NOT_FOUND;
     
                    }
     
     
    }