Pencarian Binary Pada Array

Seperti halnya pada linear search, maka binary search juga adalah metode yang umum untuk dilakukan terhadap pencarian nilai spesifik pada suatu list. Penting untuk diketahui, sebelum menggunakan metode ini, maka elemen pada array haruslah sudah diurutkan terlebih dahulu.

Diasumsikan diurutkan dengan nilai dari rendah ke tinggi, maka binary search pertama-tama akan membandingkan key atau target dengan elemen yang terletak di tengah array.
Oleh karena itu, anda bisa mempertimbangkan 3 kasus yang mungkin terjadi:
Intinya, pencarian dengan metode binary ini akan menghilangkan sekurang-kurangnya setengah dari array setelah setiap perbandingan.

Contoh:
key = 26

binary seach
binary search
Pada contoh di atas anda lihat bahwa target atau key yang dicari adalah nilai 26, dan data sudah diurutkan terlebih dahulu. Binary bekerja dengan memberikan nilai bawah, nilai tengah dan nilai atas dari array tersebut, kemudian setelah setiap perbandingan, porsi pencarian terus berkurang setengahnya, sampai dengan nilai key ditemukan.


Jika jumlah elemen array adalah z, maka setiap setelah perbandingan, akan menjadi z/2 elemen tersisa yang akan digunakan dalam pencarian, kemudian setelah perbandingan kedua, akan menjadi (z/2)/2 elemen tersisa yang digunakan dalam pencarian. Maka setelah y kali perbandingan , maka akan tersisa z/2y.

Setelah anda mengetahui dan memahami cara kerja binary search, jangan langsung terburu-buru untuk memberikan implementasi lengkap. Implementasi dilakukan secara bertahap. Anda bisa saja memulainya dengan perulangan pertama pada pencarian seperti pada gambar di atas.

Pada gambar diatas, key dibandingkan dengan nilai tengah pada list, dimana index bawah adalah 0 dan index atas adalah list.length - 1. Jika key < list[tengah], maka set index atas ke tengah - 1; jika key == list[tengah], maka key ditemukan dan kembalikan nilai tengah; jika key > list[atas], maka set index bawah ke tengah + 1.

Setelah itu barulah pertimbangkan untuk menggunakan loop untuk mengimplementasikan method. Pencarian berakhir bila key ditemukan atau jika key tidak ditemukan bila bawah > atas.

Contoh:


 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
public class Binary {
 
 public static int pencarianBinary(int[] list, int key) {
  
   int bawah = 0;
   int atas = list.length - 1;
   
   while (atas >= bawah) {
    int tengah = (bawah + atas) / 2;
    if (key < list[tengah])
     atas = tengah - 1;
    else if (key == list[tengah])
     return tengah;
    else
     bawah = tengah + 1;
    }
   return -1; // Not found
 }
 
 public static void main(String args []){
  
  int myArray [] = {5, 8, 12, 15, 17, 23, 26, 30, 34, 38, 42, 54, 64, 78, 81};
  int key1 = 26;
  int key2 = 78;
  int key3 = 8;
  int key4 = 39;
  int i = Binary.pencarianBinary(myArray, key1);
  int j = Binary.pencarianBinary(myArray, key2);
  int k = Binary.pencarianBinary(myArray, key3);
  int l = Binary.pencarianBinary(myArray, key4);
  
  System.out.println("Key " + key1 + " index " + i );
  System.out.println("Key " + key2 + " index " + j );
  System.out.println("Key " + key3 + " index " + k );
  System.out.println("Key " + key4 + " index " + l );
 }

}

Output:
Key 26 index 6
Key 78 index 13
Key 8 index 1
Key 39 index -1

Nilai 39 tidak terdapat pada myArray, oleh karena itu mengembalikan nilai -1.




Kesimpulan:

Dalam array dengan jumlah elemen yang besar, binary search akan lebih cepat dan efektif dalam melakukan pencarian key jika dibandingkan dengan linear search.

Labels: , ,