// Week 2 – Measuring running time: O(n) vs. O(log n), and O(n²)
// Run: java Timing.java
public class Timing {

    static int linearSearch(int[] a, int x) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == x) return i;
        }
        return -1;
    }

    static int binarySearch(int[] a, int x) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == x) return mid;
            if (a[mid] < x) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    // O(n²): examines every pair (are there two equal elements?)
    static boolean hasDuplicate(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] == a[j]) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println("1000 searches (worst case: the value is not in the array)");
        System.out.println("         n     linear (ms)    binary (ms)");
        for (int n = 1_000; n <= 10_000_000; n *= 10) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = 2 * i; // sorted, even numbers only

            long t0 = System.nanoTime();
            for (int r = 0; r < 1000; r++) linearSearch(a, -1);
            long t1 = System.nanoTime();
            for (int r = 0; r < 1000; r++) binarySearch(a, -1);
            long t2 = System.nanoTime();
            System.out.printf("%,10d %15.2f %14.4f%n", n, (t1 - t0) / 1e6, (t2 - t1) / 1e6);
        }

        System.out.println();
        System.out.println("hasDuplicate – O(n²): when n doubles, the time roughly quadruples");
        for (int n = 5_000; n <= 40_000; n *= 2) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = i;
            long t0 = System.nanoTime();
            hasDuplicate(a);
            long t1 = System.nanoTime();
            System.out.printf("  n = %,6d: %8.1f ms%n", n, (t1 - t0) / 1e6);
        }
    }
}