Algoritma Searching

Mencari adalah operasi paling sering dilakukan software: cari produk di katalog, cari id di database, cari kata di dokumen. Dua algoritma pencarian paling dasar — linear search dan binary search — membedakan dua dunia biaya: O(n) lawan O(log n). Pada data seribu elemen perbedaannya baru terasa nyaman; pada data sejuta elemen, linear search memeriksa hingga sejuta elemen sementara binary search selesai dalam dua puluh langkah. Bab ini mengadu keduanya dengan penghitung perbandingan eksak pada array 1024 elemen, membuktikan prasyarat yang wajib dipenuhi binary search, lalu membangun varian lowerBound yang menjadi dasar banyak operasi pada data terurut.

Linear Search Menelusuri Satu per Satu #

Linear search bekerja persis seperti namanya: periksa elemen pertama, kedua, ketiga, dan seterusnya sampai target ditemukan atau array habis. Tidak ada prasyarat — data boleh terurut, acak, bahkan berupa stream yang baru datang satu per satu. Biaya terburuknya O(n) karena target bisa berada di posisi paling akhir atau tidak ada sama sekali. Keunggulan sesungguhnya muncul pada kasus terbaik: target di indeks pertama selesai dalam 1 perbandingan, dan pada data kecil (puluhan elemen) linear search sering menang dari binary search karena tidak memikul beban perhitungan titik tengah.

Binary Search Memotong Separuh Setiap Langkah #

Binary search mensyaratkan data terurut, lalu menukar prasyarat itu dengan kecepatan: bandingkan target dengan elemen tengah, dan separuh ruang pencarian langsung dibuang. Program berikut mengukur kedua algoritma dengan penghitung perbandingan pada array 1024 elemen terurut, lalu mendemonstrasikan bencana yang terjadi bila prasyarat dilanggar:

java
PencarianLinierVsBiner.java
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;
    }
}

Output yang Dihasilkan:

text
=== Array 1024 elemen terurut, tiga target ===
target 1023 -> linier: 1023 perbandingan, biner: 10 perbandingan (indeks 1022)
target    1 -> linier:    1 perbandingan, biner: 10 perbandingan (indeks 0)
target 2000 -> linier: 1024 perbandingan, biner: 11 perbandingan (tidak ada)

=== Prasyarat binary search: data harus terurut ===
Data tak terurut : [30, 10, 50, 20, 40]
cariBiner(20)   -> indeks -1 (gagal menemukan, perbandingan: 2)
cariLinier(20)  -> indeks 3 (tetap menemukan, perbandingan: 4)

Angka pada output adalah bukti eksak yang tidak butuh kepercayaan buta. Mari kita baca tiga temuan pentingnya:

Target 1023 (indeks 1022): linear search butuh 1023 perbandingan — nyaris seluruh array — sedangkan binary search hanya 10 perbandingan. Selisih hampir seratus kali lipat pada array yang bahkan belum besar; pada array satu juta elemen selisihnya menjadi 999999 lawan 20.
Target 1 (indeks 0): linear search menang telak dengan 1 perbandingan — kasus terbaiknya — sementara binary search tetap menghabiskan 10 perbandingan karena target di ujung kiri dipotong satu per satu. Binary search unggul di kasus terburuk dan rata-rata, bukan di semua titik.
Target 2000 (tidak ada): linear memeriksa seluruh 1024 elemen; binary selesai dalam 11 perbandingan karena 2¹⁰ = 1024, ruang pencarian tinggal satu elemen setelah sepuluh pemotongan, dan perbandingan kesebelas memastikan elemen terakhir pun bukan target. Jumlah maksimum perbandingan binary search pada n elemen adalah ⌊log₂ n⌋ + 1.

Lower Bound Mencari Batas Bawah #

Varian binary search yang paling berguna di dunia nyata bukan sekadar “ada atau tidak”, melainkan posisi sisip: indeks elemen pertama yang nilainya ≥ target. Method lowerBound memakai rentang setengah terbuka [lo, hi) — hi berangkat dari a.length sehingga jawaban “semua elemen lebih kecil” pun punya tempat, yaitu di akhir array:

java
LowerBound.java
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;
    }
}

Output yang Dihasilkan:

text
Data terurut: [10, 20, 20, 30, 40, 50]

=== lowerBound: indeks elemen pertama >= target ===
lowerBound(20) = 1, elemen di sana: 20
lowerBound(25) = 3, elemen di sana: 30
lowerBound(55) = 6, elemen di sana: (akhir array)
lowerBound( 5) = 0, elemen di sana: 10

=== Arrays.binarySearch dari pustaka Java ===
binarySearch(25) = -4 -> titik sisip 3 (sama dengan lowerBound: true)
binarySearch(20) =  2 (ditemukan)
binarySearch(60) = -7 -> titik sisip 6 (sama dengan lowerBound: true)

Perhatikan tiga perilaku dari output: lowerBound(20) mengembalikan 1 — indeks kemunculan pertama dari nilai 20, bukan indeks duplikat keduanya; lowerBound(25) mengembalikan 3 karena 25 tidak ada dan posisi sisip yang tepat adalah sebelum nilai 30; lowerBound(55) mengembalikan 6 — panjang array, penanda “semua elemen lebih kecil”. Pustaka Java memakai konvensi yang sama: Arrays.binarySearch mengembalikan nilai negatif -(titik sisip) - 1 ketika target tidak ditemukan, sehingga pemanggil bisa memulihkan titik sisip dengan -hasil - 1 — output program memverifikasi bahwa titik sisip tersebut identik dengan hasil lowerBound kita.

Bedah singkat inti lowerBound:

Baris 51-53 (hi = a.length): rentang setengah terbuka [lo, hi) membuat semua kasus batas seragam — jawaban selalu berada di [0, a.length] tanpa perlu kasus khusus untuk array penuh elemen kecil.
Baris 58-63 (dua cabang): ketika a[mid] < target, seluruh bagian kiri termasuk mid pasti lebih kecil, jadi lo = mid + 1. Ketika a[mid] >= target, mid masih kandidat jawaban, jadi hi = mid — batas ditarik ke mid tanpa melewatkannya. Loop berhenti ketika lo == hi, dan posisi itulah jawabannya.
Ketidakpastian duplikat: Arrays.binarySearch tidak menjamin indeks mana dari elemen kembar yang dikembalikan (output kita kebetulan mendapat indeks 2), sedangkan lowerBound selalu mengembalikan kemunculan pertama — sifat yang dibutuhkan operasi rentang seperti “semua nilai ≥ x”.

Pencarian biner bekerja karena data terurut; ironisnya, mengurutkan data justru lebih mahal dari sekali pencarian — O(n log n) lawan O(log n). Bab berikutnya masuk ke dalam mesin pengurutan itu sendiri: keluarga algoritma sorting dari bubble sort yang sederhana sampai quick sort yang menopang Arrays.sort.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

java
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;
    }
}

java
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;
    }
}