import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Random;

public class Main {

    public static void main(String[] args)
    {
        int[] sizes = {128_000, 256_000, 512_000, 1_024_000, 2_048_000, 4_096_000, 8_192_000, 16_384_000,
                32_768_000, 65_536_000};

        Random random = new Random();
        Search.dummy();

        long time1 = System.nanoTime();

        System.out.println("\nLinear search - value IS in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }
            int value = A[random.nextInt(A.length)];

            long t1 = System.nanoTime();
            int index = Search.linearSearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nLinear search - value IS NOT in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt(10_000);
            }
            int value = 20_000;

            long t1 = System.nanoTime();
            int index = Search.linearSearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search - value IS in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }
            int value = A[random.nextInt(A.length)];

            long t1 = System.nanoTime();
            Arrays.sort(A);
            int index = Search.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search - value IS NOT in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt(10_000);
            }
            int value = 20_000;

            long t1 = System.nanoTime();
            Arrays.sort(A);
            int index = Search.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search already sorted - value IS in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }
            int value = A[random.nextInt(A.length)];

            long t1 = System.nanoTime();
            int index = Search.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search already sorted - value IS NOT in the array");
        for (int size : sizes) {
            int[] A = new int[size];

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

            long t1 = System.nanoTime();
            int index = Search.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search Java - value IS in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }
            int value = A[random.nextInt(A.length)];

            long t1 = System.nanoTime();
            Arrays.sort(A);
            int index = Arrays.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search Java - value IS NOT in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt(10_000);
            }
            int value = A.length;

            long t1 = System.nanoTime();
            Arrays.sort(A);
            int index = Arrays.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search Java already sorted - value IS in the array");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }
            int value = A[random.nextInt(A.length)];

            long t1 = System.nanoTime();
            int index = Arrays.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBinary search Java already sorted - value IS NOT in the array");
        for (int size : sizes) {
            int[] A = new int[size];

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

            long t1 = System.nanoTime();
            int index = Arrays.binarySearch(A, value);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        long time2 = System.nanoTime();
        System.out.println("\nTotal time: " + ((time2 - time1) / 1e9) + " seconds");
    }

    public static String printNumber(double value)
    {
        DecimalFormat df = new DecimalFormat("###,###,###");
        return df.format(value);
    }
}