Pencarian (Java)

Ada algoritma sederhana yang bisa digunakan untuk mencari suatu item pada array : Lihat setiap array, dan cek apakah isinya sama dengan item yang kita cari. Jika ketemu, maka pencarian selesai. Jika kita sudah melihat semua item dan tidak ada item yang sama, maka kita yakin bahwa item yang kita cari tidak ada dalam array.

Subrutin untuk mengimplementasikan algoritma tersebut mudah kita tulis. Misalnya array yang kita cari bertipe int[]. Berikut ini adalah metode untuk mencari integer tertentu dalam array. Jika integer ditemukan, maka metode ini akan mengembalikan indeks dalam array di mana item tersebut ditemukan. Jika integer tersebut tidak ada dalam array, maka metode tersebut akan mengembalikan nilai -1, yang artinya integer tersebut tidak ditemukan.

static int cari(int[] A, int N) {
    // Mencari integer N di dalam array A
    // Kondisi akhir : jika N tidak ada dalam array
    //     maka kembalikan -1. Jika N ada dalam array
    //     kembalikan i, yaitu indeks di mana A[i] == N
 
    for (int indeks = 0; indeks < A.length; indeks++) {
        if ( A[indeks] == N )
            return indeks;  // N ditemukan pada indeks ini.
    }
 
    // Jika kita sampai di sini, berarti N belum ditemukan
    // Kembalikan -1.
 
    return -1;
}

Metode seperti ini dimana pencarian dilakukan dengan menguji setiap item disebut pencarian linier (linear search). Jika kita tidak mengetahui apa-apa tentang isi dan urutan item pada array, maka tidak ada lagi algoritma alternatif yang lebih baik dari ini. Akan tetapi jika kita tahu bahwa elemen di dalam array diurut dalam urutan menaik atau urutan menurun, maka kita bisa menggunakan algoritma lain yang lebih cepat. Tentu saja, waktu yang dibutuhkan untuk mengurutkan array tidak sebentar, akan tetapi jika array ini akan dicari berulang kali, maka waktu pengurutan array akan terbayarkan dengan cepat.

Pencarian biner (binary search) adalah metode untuk mencari suatu item dalam array yang sudah diurutkan. Meskipun implementasinya tidak mudah, akan tetapi ide dasarnya sangat mudah : Jika kita mencari suatu item dalam suatu array yang terurut, maka kita bisa menghapus setengah dari keseluruhan elemen hanya dengan melihat satu nilai. Misalnya kita ingin mencari bilangan 42 dalam array yang sudah diurutkan yang terdiri dari 1000 bilangan bulat. Anggap bahwa array tersebut diurutkan dalam urutan menaik (dari kecil ke besar). Kemudian kita cek item ke-500 dalam array, dan ternyata isinya adalah 93. Karena 42 kurang dari 93, dan karena elemen di dalam array tersebut dalam urutan menaik, kita bisa simpulkan bahwa 42 tidak mungkin ada di item ke-501 ke atas. Maka elemen tersebut pasti ada di lokasi tertentu sebelum posisi ke-500.

Cara berikutnya adalah melihat di lokasi 250. Jika misanya lokasi tersebut berisi 21, maka kita bisa menghilangkan lokasi 0 hingga 250 dan memfokuskan pencarian antara 251 dan 499. Yang berikutnya adalah kira-kira di lokasi ke-125 setelah itu, yang berikutnya adalah sekitar 62 lokasi setelah itu. Setelah kira-kira 10 langkah pengujian, hanya ada satu lokasi yang akan kita cek.

Cara ini akan jauh lebih mudah dan lebih cepat daripada harus mencari semua elemen di dalam array. Jika ada satu juta elemen di dalam array, maka kita hanya perlu mencari 20 kali. (Secara matematika, jumlah langkah yang diperlukan adalah logaritmik dari jumlah item di dalam array).

Untuk membuat subrutin pencarian biner pada Java yang mencari item N pada array A, kita hanya perlu mencatat rentang lokasi di mana kira-kira N bisa ditemukan. Pada setiap langkah, kita bisa mengurangi kemungkinan dan mengurangi rentang pencarian. Operasi dasarnya adalah mencari item di tengah-tengah rentang tersebut. Jika item ini lebih besar dari N, maka rentang bagian atasnya bisa dibuang. Jika kurang dari N, maka rentang bawahnya bisa dibuang.

Jika nilai di tengah-tengah tersebut persisi sama denan N, maka pencarian selesai. Jika ukurang pencarian berkurang menjadi nol, maka nilai N tidak ada dalam array. Berikut ini adalah subrutin yang mengembalikan lokasi di mana N berada di dalam array terurut A. Jika N tidak ditemukan, maka nilai -1 akan dikembalikan.

static int pencarianBiner(int[] A, int N) {
    // Mencari bilangan N pada array A
    // Kondisi awal : A harus diurut menaik (dari kecil ke besar)
    // Kondisi akhir : Jika N ada dalam array, maka kembalikan
    //    nilai i, di mana A[i] == N. Jika tidak kembalikan -1
 
    int lokasiTerkecil = 0;
    int lokasiTerbesar = A.length - 1;
 
    while (lokasiTerbesar >= lokasiTerkecil) {
        int tengah = (lokasiTerkecil + lokasiTerbesar) / 2;
        if (A[tengah] == N) {
            // N ditemukan di sini
            return tengah;
        }
        else if (A[tengah] > N) {
            // buang lokasi >= tengah
            lokasiTerbesar = tengah - 1;
        }
        else {
            // buang lokasi <= tengah
            lokasiTerkecil = tengah + 1;
        }
    }
 
    // Sampai titik ini, lokasiTerbesar < lokasiTerkecil
    // yang berarti nilai N tidak ada dalam array.
    // Kembalikan -1, yang artinya item tidak ditemukan
 
    return -1;
}