import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

/**
 * A class for searching integers.
 */
public class Search
{
    /**
     * The number of elements we looked at.
     */
    private static int numElementsComparedAgainst = 0;

    public static final void main(String[] args)
    {
        // Load 2 data files into 2 arrays, the first unsorted, the second
        // sorted.
        int[] unsortedArray = loadFileIntoArray("unsorted-set.txt");
        int[] sortedArray = loadFileIntoArray("sorted-set.txt");

        // TODO write your code here
        // Prompt the user for a number to look for
        // then display the results as well as the execution time.
        
        // Here is sample code for how to record execution time.
        long startTimeNanos = 0, totalTimeSecs = 0;
        int k = 2, index = -1;

        startTimeNanos = System.nanoTime();
        index = sequentialSearch(unsortedArray, k);
        totalTimeSecs = (System.nanoTime() - startTimeNanos) / 1000000000;
        System.out.println(
            "The number " + k + 
            " was found at index " + index + 
            " in " + totalTimeSecs + " seconds using sequential search.");

        startTimeNanos = System.nanoTime();
        index = binarySearch(unsortedArray, k);
        totalTimeSecs = (System.nanoTime() - startTimeNanos) / 1000000000;
        System.out.println(
            "The number " + k + 
            " was found at index " + index + 
            " in " + totalTimeSecs + " seconds using binary search.");
    }

    /**
     * Loads the file fileName into an integer array
     */
    public static int[] loadFileIntoArray(String fileName)
    {
        // we don't care about exceptions, so just consume it
        Scanner scanner = null;
        try
        {
            scanner = new Scanner(new File(fileName));
        }
        catch (FileNotFoundException ex)
        {
            ex.printStackTrace();
        }
        
        // First get the number of lines in the file, which is the first line
        int size = Integer.parseInt(scanner.nextLine());

        // Now we can initialize the array
        int[] a = new int[size];

        // And read in the rest of the data
        int counter = 0;
        while (scanner.hasNext())
        {
            a[counter] = Integer.parseInt(scanner.nextLine());
            counter ++;
        }

        return a;
    }

    /**
     * Uses the sequential search algorithm to find the number k.
     * Remember to reset numElementsComparedAgainst each time!
     * Returns the position in which the number was found. If the number is
     * not in the array, returns -1.
     */
    public static int sequentialSearch(int[] array, int k)
    {
        numElementsComparedAgainst = 0;

        return -1;
    }

    /**
     * Uses the binary search algorithm to find the number k.
     * Remember to reset numElementsComparedAgainst each time!
     * Returns the position in which the number was found. If the number is
     * not in the array, returns -1.
     *
     * Consider writing a recursive method to do this.
     */
    public static int binarySearch(int[] array, int k)
    {
        numElementsComparedAgainst = 0;

        return -1;
    }

    /**
     * A template for recursive binary search.
     */
    public static int binarySearch(int[] array, int start, int end, int k)
    {
        return -1;
    }
}