public class MenghitungOperasi {

    // Penghitung operasi dasar: deterministik, tidak memakai jam/pengukuran waktu.
    static long operasi = 0;

    public static void main(String[] args) {
        int n = 1000;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1; // 1..1000, sudah terurut
        }

        System.out.println("=== Operasi dasar pada array " + n + " elemen ===");

        operasi = 0;
        int maks = cariMaks(data);
        System.out.println("cariMaks        -> hasil " + maks
                + ", perbandingan elemen: " + operasi);

        operasi = 0;
        long pasangan = hitungPasangan(data);
        System.out.println("hitungPasangan  -> hasil " + pasangan
                + ", iterasi loop dalam: " + operasi);

        operasi = 0;
        int indeksBiner = cariBiner(data, 1000);
        System.out.println("cariBiner(1000) -> indeks " + indeksBiner
                + ", perbandingan: " + operasi);

        operasi = 0;
        int indeksLinier = cariLinier(data, 1000);
        System.out.println("cariLinier(1000)-> indeks " + indeksLinier
                + ", perbandingan: " + operasi);

        System.out.println();
        System.out.println("=== Kasus terbaik, terburuk, rata-rata (n=100) ===");
        demoKasus();
    }

    static int cariMaks(int[] a) {
        int maks = a[0];
        for (int i = 1; i < a.length; i++) {
            operasi++;              // satu perbandingan elemen
            if (a[i] > maks) {
                maks = a[i];
            }
        }
        return maks;
    }

    static long hitungPasangan(int[] a) {
        long jumlah = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                operasi++;          // satu iterasi loop dalam
                jumlah += a[i] + a[j];
            }
        }
        return jumlah;
    }

    static int cariLinier(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            operasi++;              // satu perbandingan elemen
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }

    static int cariBiner(int[] a, int target) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            operasi++;              // satu perbandingan dengan elemen tengah
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    static void demoKasus() {
        int n = 100;
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i + 1;
        }

        operasi = 0;
        cariLinier(data, 1);        // target berada di indeks 0
        long terbaik = operasi;

        operasi = 0;
        cariLinier(data, 100);      // target berada di indeks terakhir
        long terburuk = operasi;

        operasi = 0;
        cariLinier(data, 999);      // target tidak ada di array
        long tidakAda = operasi;

        long total = 0;
        for (int target = 1; target <= n; target++) {
            operasi = 0;
            cariLinier(data, target);
            total += operasi;
        }
        double rata = (double) total / n;

        System.out.printf("Target di indeks 0  : %d perbandingan (kasus terbaik)%n", terbaik);
        System.out.printf("Target di indeks %d: %d perbandingan (kasus terburuk)%n", n - 1, terburuk);
        System.out.printf("Target tidak ada    : %d perbandingan (kasus terburuk)%n", tidakAda);
        System.out.printf("Rata-rata 100 target: %.1f perbandingan%n", rata);
    }
}