Pencarian Binary Pada Array

Seperti halnya pada linear search, maka binary search juga ialah metode yang umum untuk dilakukan terhadap pencarian nilai spesifik pada suatu list. Penting untuk diketahui, sebelum memakai 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 sasaran dengan elemen yang terletak di tengah array.
Oleh sebab itu, anda sanggup mempertimbangkan 3 kasus yang mungkin terjadi:

• Jika key kurang dari elemen tengah, maka anda hanya perlu mencari key hanya untuk setengah penggalan pertama dari array.
• Jika key ialah elemen tengah, maka pencarian eksklusif berakhir atau sasaran eksklusif ditemukan.
• Jika key lebh besar dari elemen tengah, maka anda hanya perlu melanjutkan pencarian untuk key hanya untuk setengah penggalan kedua dari array.

Intinya, pencarian dengan metode binary ini akan menghilangkan sekurang-kurangnya setengah dari array sehabis setiap perbandingan.

Contoh:
key = 26

binary search

Pada teladan di atas anda lihat bahwa sasaran atau key yang dicari ialah nilai 26, dan data sudah diurutkan terlebih dahulu. Binary bekerja dengan memperlihatkan nilai bawah, nilai tengah dan nilai atas dari array tersebut, lalu sehabis setiap perbandingan, porsi pencarian terus berkurang setengahnya, hingga dengan nilai key ditemukan.


Jika jumlah elemen array ialah z, maka setiap sehabis perbandingan, akan menjadi z/2 elemen tersisa yang akan dipakai dalam pencarian, lalu sehabis perbandingan kedua, akan menjadi (z/2)/2 elemen tersisa yang dipakai dalam pencarian. Maka setelah y kali perbandingan , maka akan tersisa z/2^y.

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

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

Setelah itu barulah pertimbangkan untuk memakai loop untuk mengimplementasikan method. Pencarian berakhir bila key ditemukan atau jikalau 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 sebab itu mengembalikan nilai -1.




Kesimpulan:

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

Bagikan Artikel ini