public class PencarianLinierVsBiner {

    // Penghitung perbandingan elemen: angka eksak, bukan estimasi.
    static long perbandingan;

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

        System.out.println("=== Array " + n + " elemen terurut, tiga target ===");

        uji(data, 1023);   // berada di dekat ujung kanan
        uji(data, 1);      // berada di ujung kiri
        uji(data, 2000);   // tidak ada di array

        System.out.println();
        System.out.println("=== Prasyarat binary search: data harus terurut ===");
        int[] acak = {30, 10, 50, 20, 40};

        perbandingan = 0;
        int hasilBiner = cariBiner(acak, 20);
        System.out.println("Data tak terurut : [30, 10, 50, 20, 40]");
        System.out.println("cariBiner(20)   -> indeks " + hasilBiner
                + " (gagal menemukan, perbandingan: " + perbandingan + ")");

        perbandingan = 0;
        int hasilLinier = cariLinier(acak, 20);
        System.out.println("cariLinier(20)  -> indeks " + hasilLinier
                + " (tetap menemukan, perbandingan: " + perbandingan + ")");
    }

    static void uji(int[] data, int target) {
        perbandingan = 0;
        int indeksLinier = cariLinier(data, target);
        long linier = perbandingan;

        perbandingan = 0;
        int indeksBiner = cariBiner(data, target);
        long biner = perbandingan;

        String status = indeksLinier >= 0 ? "indeks " + indeksLinier : "tidak ada";
        System.out.printf("target %4d -> linier: %4d perbandingan, "
                + "biner: %2d perbandingan (%s)%n",
                target, linier, biner, status);
    }

    static int cariLinier(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            perbandingan++;          // satu pemeriksaan 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;
            perbandingan++;          // satu perbandingan dengan elemen tengah
            if (a[mid] == target) {
                return mid;
            }
            if (a[mid] < target) {
                lo = mid + 1;        // buang separuh kiri
            } else {
                hi = mid - 1;        // buang separuh kanan
            }
        }
        return -1;
    }
}