Banner Java

Mencari Elemen Larik (Array) Dengan Pendekatan Binary Search

Tidak kalah penting dari proses pengurutan elemen larik adalah proses mencari elemen tertentu di larik. Pegawai bank perlu mencari nomor rekening nasabah untuk melakukan perubahan data terbaru. Sebuah mesin ATM perlu mencari nomor pin kartu ATM yang dimasukkan untuk dapat mengambil data saldo uang yang masih tersisa. Mencari elemen tertentu di larik adalah proses yang juga umum dalam pemrograman komputer.

Selain Mencari Elemen Larik (Array) Dengan Pendekatan Linear Search, Anda juga dapat menggunakan pendekatan binary search. Binary search jauh lebih efektif untuk mencari elemen larik dengan jumlah elemen besar. Untuk mencari nilai kunci yang berada di dalam larik menggunakan binary search, elemen larik harus dalam keadaan terurut (sorted). Binary search dapat mempersingkat waktu eksekusi kode program untuk mencari elemen larik.

Di iterasi pertama perulangan for, pendekatan binary search akan membandingkan nilai kunci dengan elemen larik yang berada di posisi tengah (middle element). Apabila nilai kunci sama dengan nilai elemen larik yang berada di posisi tengah, berarti telah ditemukan kecocokan. Apabila nilai kunci tidak cocok dengan elemen larik yang berada di posisi tengah dan nilai kunci lebih kecil dari nilai elemen yang berada di tengah, Anda cukup membandingkan nilai kunci dengan elemen larik pertama sampai dengan indek elemen larik tengah dikurangi 1 (elemen larik yang berada di tengah tidak disertakan karena sudah tidak cocok dengan nilai kunci). Apabila nilai kunci lebih besar dari nilai elemen tengah, Anda cukup membandingkan nilai kunci dengan indek elemen larik tengah ditambah 1 sampai dengan elemen larik terakhir.

Kalau belum ditemukan kecocokan pada iterasi pertama, apabila nilai kunci lebih kecil dari nilai tengah, maka elemen pertama larik tetap sama dan indek elemen tengah larik dikurangi 1 akan menjadi elemen terakhir larik. Apabila nilai kunci lebih besar dari elemen tengah, maka indek elemen tengah larik ditambah 1 akan menjadi elemen pertama dan elemen terakhir larik tetap sama. Pola ini terus berlangsung di setiap iterasi sampai ditemukan atau tidak ditemukan kecocokan. Bila tidak ditemukan kecocokan, metoda akan mengembalikan nilai -1. Berikut ini adalah contoh program untuk mencari elemen di larik menggunakan pendekatan binary search.

// Nama file : BinarySearch.java
// Mencari nilai elemen dengan metoda binary search

// Mengimpor kelas
import javax.swing.JOptionPane;
import javax.swing.JTextArea;
import java.util.Arrays;

// Deklarasi kelas
public class BinarySearch {

   // Metoda main
   public static void main(String[] args) {

      String tampilan;
      JTextArea areaTampilan;
      int nilai;
      int indek;

      // Mendeklarasikan, membuat, menginisialisasi
      // dan menampilkan elemen larik
      int[] nilaiInt = {4, 10, 8, 6, 7, 1, 5, 3, 9, 2};
      tampilan = "Menampilkan nilai elemen larik sesuai urutan aslinya :\n";
      for (int x = 0; x < nilaiInt.length; x++)
         tampilan += nilaiInt[x] + "   ";
 
      // Menampilkan larik setelah diurutkan
      Arrays.sort(nilaiInt);
      tampilan += "\nMenampilkan nilai elemen larik setelah diurut :\n";
      for (int x = 0; x < nilaiInt.length; x++)
         tampilan += nilaiInt[x] + "   ";

      // Nilai elemen dicari dan pemanggilan metoda
      nilai = 5;
      indek = mencariDenganBS(nilaiInt, nilai);

      // Menampilkan hasil
      tampilan += "\nNilai elemen yang dicari : " + nilai;
      tampilan += "\nNilai ditemukan pada indek : " + indek;
      areaTampilan = new JTextArea();
      areaTampilan.setText(tampilan);
      JOptionPane.showMessageDialog(null, areaTampilan, "Binary Search",
         JOptionPane.INFORMATION_MESSAGE);

      // Mengakhiri aplikasi
      System.exit(0);
  
   } // Akhir blok metoda main

   // Metode dengan pendekatan binary search
   public static int mencariDenganBS(int[] larikC, int nilaiDicari) {
      
      int bawah = 0;
      int atas =larikC.length - 1;

      while (atas >= bawah) {
         int tengah = (bawah + atas) / 2;
         if (nilaiDicari < larikC[tengah])
            atas = tengah - 1;
         else if (nilaiDicari == larikC[tengah])
            return tengah;
         else
            bawah = tengah + 1;
      }
      
      return -1;

   } // Akhir blok metoda mencariDenganBS
}

Baris nomor 51 – 68 adalah metoda mencariDenganBS untuk mencari elemen di larik menggunakan pendekatan binary search. Di perulangan while, larikC adalah larik yang nilai elemennya dicocokkan dengan nilai kunci, nilaiDicari adalah nilai kunci yang akan dicocokkan dengan nilai elemen di larikC. Variabel bawah menunjukkan indek pertama larik, variabel atas menunjukkan indek terakhir larik, veriabel tengah menunjukkan indek di posisi tengah antara indek pertama (variabel bawah) dan indek terakhir (variabel atas). Apabila nilaiDicari < larikC[tengah], perlu diatur agar atas = tengah – 1. Apabila nilaiDicari == larikC[tengah] berarti telah ditemukan kecocokan dan metoda akan mengembalikan indek elemen tengah larik berupa nilai variabel tengah. Apabila nilaiDicari > larikC[tengah], perlu diatur agar bawah = tengah + 1.

Mencari elemen larik

Baca artikel terkait lainnya:

Untuk memperbaiki mutu konten, Anda dapat berpartisipasi dengan cara melaporkan apabila menemukan kesalahan ketik, kata-kata rangkap, redaksi kurang pas (jelas), gambar pendukung tidak ada dan sebagainya melalui form Kontak Kami untuk mendapatkan perbaikan. Terima kasih atas kerjasamanya.

Hindro HindriantoHindro adalah pendiri sekaligus admin termasmedia.com dan topikit.com, blog online yang mengulas teknologi informasi. Dunia web mulai ditekuni tahun 2012 dengan mempelajari CMS Joomla dan Wordpress. Beberapa buku yang sekarang dipelajari antara lain PHP, HTML5, ASP.NET 4.5, JavaScript, CSS3, MySQL, Adobe Dreamweaver, Adobe Photoshop dan Adobe Flash.