import java.util.Arrays;

public class LowerBound {

    public static void main(String[] args) {
        int[] data = {10, 20, 20, 30, 40, 50};
        System.out.println("Data terurut: " + Arrays.toString(data));

        System.out.println();
        System.out.println("=== lowerBound: indeks elemen pertama >= target ===");
        int[] targetUji = {20, 25, 55, 5};
        for (int target : targetUji) {
            int indeks = lowerBound(data, target);
            String isi = indeks == data.length ? "(akhir array)" : String.valueOf(data[indeks]);
            System.out.printf("lowerBound(%2d) = %d, elemen di sana: %s%n",
                    target, indeks, isi);
        }

        System.out.println();
        System.out.println("=== Arrays.binarySearch dari pustaka Java ===");
        for (int target : new int[] {25, 20, 60}) {
            int hasil = Arrays.binarySearch(data, target);
            if (hasil >= 0) {
                System.out.printf("binarySearch(%2d) = %2d (ditemukan)%n", target, hasil);
            } else {
                int titikSisip = -hasil - 1;
                System.out.printf("binarySearch(%2d) = %2d -> titik sisip %d "
                        + "(sama dengan lowerBound: %s)%n",
                        target, hasil, titikSisip,
                        titikSisip == lowerBound(data, target));
            }
        }
    }

    // Indeks pertama yang elemennya >= target; jika tidak ada, panjang array.
    static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;           // hi eksklusif: rentang [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;        // jawaban pasti di kanan mid
            } else {
                hi = mid;            // mid masih kandidat: tahan sebagai batas
            }
        }
        return lo;
    }
}