import java.util.Arrays;
import java.util.Random;

public class TimingSearch {

    public static final Random RAND = new Random();

    public static void main(String[] args) {
        long begin, timeLS, timeSLS, timeBS;
        int[] numbers;
        int target;

        // get started
        printIntroduction();
        numbers = makeIntArray();
        target = getTarget();

        // time linear search
        begin = System.nanoTime();
        linearSearch(numbers, target);
        timeLS = System.nanoTime() - begin;

        // sort array for remaining searches
        Arrays.sort(numbers);

        // time sorted linear search
        begin = System.nanoTime();
        sortedLinearSearch(numbers, target);
        timeSLS = System.nanoTime() - begin;

        // time binary search
        begin = System.nanoTime();
        binarySearch(numbers, target);
        timeBS = System.nanoTime() - begin;

        // report results
        System.out.println("Timing Results:");
        System.out.printf("%25s: %,20d%n", "Linear Search", timeLS);
        System.out.printf("%25s: %,20d%n", "Sorted Linear Search", timeSLS);
        System.out.printf("%25s: %,20d%n", "Binary Search", timeBS);
    }

    // Print an introduction
    private static void printIntroduction() {
        System.out.println("\n"
                + "Comparing Search Times\n"
                + "----------------------\n\n"
                + "This program compares the amount of time it takes "
                + "to search a large array for a\ntarget number. "
                + "Run it multiple times to see how the timing data varies.");
    }

    // Create a large array of large numbers
    private static int[] makeIntArray() {
        int[] result = new int[100000];
        for (int i = 0; i < result.length; ++i) {
            result[i] = getTarget();
        }
        return result;
    }

    // create a large number, randomly
    private static int getTarget() {
        return RAND.nextInt(0, Integer.MAX_VALUE);
    }

    // search an unsorted array for a value
    private static boolean linearSearch(int[] numbers, int target) {
        for (int number : numbers) {
            if (number == target) {
                return true;
            }
        }
        return false;
    }

    // search a sorted array for a value, linearly
    private static boolean sortedLinearSearch(int[] numbers, int target) {
        for (int number : numbers) {
            if (number == target) {
                return true;
            } else if (number > target) {
                return false;
            }
        }
        return false;
    }

    // search a sorted array for a value using binary split
    private static boolean binarySearch(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int diff = target - numbers[mid];
            if (diff < 0) {
                // target is smaller
                high = mid;
            } else if (diff > 0) {
                // target is larger
                low = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }

}