Mencari elemen larik (array) dengan pendekatan binary search di Java

Mencari Elemen Larik (Array) Dengan Pendekatan Binary Search Di Java

Tidak kalah penting dari proses mengurutkan elemen larik adalah proses mencari elemen tertentu di larik. Mencari elemen tertentu di larik adalah proses yang juga umum dalam pemrograman komputer. Ada dua pendekatan yang populer digunakan dalam mencari elemen larik yaitu pendekatan linear search dan binary search.

Mencari elemen larik dengan pendekatan linear search hanya efektif bila jumlah elemen larik sedikit. Untuk jumlah elemen larik yang banyak, Anda perlu menggunakan pendekatan binary search. Untuk mencari nilai kunci yang ada di larik menggunakan binary search, elemen larik harus sudah terurut (sorted). Binary search dapat mempersingkat waktu eksekusi kode program untuk mencari elemen larik.

Pendekatan binary search akan membandingkan nilai kunci atau nilai yang dicari dengan elemen larik yang berada di posisi tengah. Bila nilai kunci sama dengan nilai elemen larik di posisi tengah, berarti telah ditemukan kecocokan.

Bila nilai kunci tidak cocok dengan elemen larik 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 di tengah tidak disertakan karena sudah tidak cocok dengan nilai kunci).

Baca artikel:

Bila 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. Bila belum ditemukan kecocokan pada iterasi pertama, bila 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.

Baca artikel:

Bila nilai kunci lebih besar dari elemen tengah, maka indek elemen tengah larik ditambah 1 akan menjadi elemen pertama sedangkan 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 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
}

Mencari elemen larik (array) di Java dengan pendekatan binary search

Baris nomor 51 – 68 adalah blok metoda mencariDenganBS untuk mencari elemen di larik menggunakan pendekatan binary search. Di perulangan while, larikC adalah larik yang nilai elemennya dicocokkan dengan nilai kunci atau nilai yang dicari, nilaiDicari adalah nilai kunci yang akan dicocokkan dengan nilai elemen di larikC.

Baca artikel Menyalin Elemen Larik Menggunakan Metoda arrayCopy Di Java

Variabel bawah adalah indek pertama larik, variabel atas adalah indek terakhir larik dan veriabel tengah adalah indek di posisi tengah antara indek pertama (variabel bawah) dan indek terakhir (variabel atas). Bila nilaiDicari < larikC[tengah], perlu diatur agar atas = tengah – 1. Bila nilaiDicari == larikC[tengah] berarti telah ditemukan kecocokan dan metoda akan mengembalikan indek elemen tengah larik berupa nilai variabel tengah. Bila nilaiDicari > larikC[tengah], perlu diatur agar bawah = tengah + 1.

SUKAI DAN BAGIKAN ARTIKEL INI:
Pin It