Dalam pemrograman, pencarian data merupakan suatu hal yang sangat gampang dilakukan. Anda sebagai programmer bisa menggunakan beberapa teknik pemrograman sederhana seperti, Teknik Pengkondisian (IF). Lalu, apakah segampang itu melakukan pencarian Data yang banyak? Sebenarnya itu bisa gampang jikalau Datanya masih sedikit namun, bagaimana kalau Datanya sangat banyak seperti mesin pencari Google. Bisa Anda bayangkan bagaimana banyaknya Data yang tersimpan dalam database-nya dan kok bisa hanya dalam beberapa detik apa yang kita cari langsung bisa muncul di hadapan Anda. Sebenarnya, dalam pencarian (searching) ada beberapa teknik yang bisa Anda gunakan seperti, Sequential Searching dan Binnary Searching.
Pada artikel ini, saya akan membahas metode Binnary Searching. “Apa itu Binnary Searching?” Binnary Searching merupakan suatu metode pencarian dimana, Data yang dicari akan dibagi menjadi 2 bagian dan seterusnya akan dibagi menjadi 2 bagian sampai Data yang dicari benar-benar ditemukan. Sebelum masuk ke contoh kasus, berikut adalah aturan yang berlaku dalam proses Binnary Searching.
1. Jika nilai Data ke-n lebih besar dari Data yang dicari maka, index_tengah di kurang 1 atau (Data-N > Data Cari → Index_tengah--) dan simpan ke nilai akhir.
2. Jika nilai Data ke-n lebih kecil dari Data yang dicari maka, index_tengah di tambah 1 atau (Data-N < Data Cari → Index_tengah++) dan simpan ke nilai awal.
3. Jika nilai Data ke-n ditemukan maka, cetak nilai iterasinya.
Catatan, bahwa sebelum melakukan proses pencarian di Binnary Searching Data terlebih dahulu di sorting secara Ascending.
Dan berikut ialah contoh kasusnya.
Data : 12 9 3 4 20 1 -5
Data yang dicari : 1
Proses Binnary Searching :
1. Sorting terlebih dahulu Data secara Ascending.
2. Buatlah tabel berikut.
3. Setelah itu lakukan proses Binnary Searching. Perhatikan tabel berikut.
Penjelasan Proses Binnary Searching
- Untuk iterasi ke-1, selalu isi nilai Index_Awal dengan 0 dan nilai Index_Akhir dengan nilai Index Terakhir sesuai dengan jumlah Data. Kemudian, Index_Tengah = (Index_Awal + Index_Akhir) / 2. Untuk contoh diatas, Index_Tengah = (0 + 6) / 2 = (6) / 2 = 3. Nilai Data dengan Index 3 ialah 4. Catatan, Data yang akan dipakai dalam proses Binnary Searching ialah Data yang sudah di Sorting.
- Bandingkan Data yang dicari dengan nilai Data. Karena 4 lebih besar dari 1 atau (Data ke-n lebih besar dari Data yang dicari) maka, untuk iterasi berikutnya ubah Index_Akhir menjadi Index_Akhir = Index_Tengah – 1. Untuk langkah ini, lebih baik Anda baca lagi peraturan yang ada dalam proses Binnary Searching yang sudah saya jelaskan diatas.
- Untuk iterasi ke-2, nilai Index_Awal tetap 0 (Karena, nggak ada perubahan). Nilai Index_Akhir = 2 (Karena, pada iterasi sebelumnya Data-n > Data_Cari). Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (0 + 2) / 2 = (2) / 2 = 1. Nilai Data dengan Index 1 ialah 1. Data yang dicari = 1 dan Data ke-n = 1 maka, Data ditemukan.
- Proses Pencarian berhenti dan cetak “Data dengan nilai 1 ditemukan pada iterasi ke-2”.
Gimana ??? masih belum paham ya ??? Ini saya berikan 1 contoh kasus lagi dengan Data yang sama namun, nilai yang dicari berbeda.
Data : 12 9 3 4 20 1 -5
Data yang dicari : 12
Proses Binnary Searching :
1. Sorting terlebih dahulu Data secara Ascending
2. Buatlah tabel berikut
3. Setelah itu, lakukan proses Binnary Searching. Seperti pada tabel berikut.
Penjelasan Proses Binnary Searching
- Untuk iterasi ke-1, Index_Awal = 0 (Untuk iterasi ke-1, index_awal memang harus 0). Index_Akhir = 6 (Sesuaikan dengan jumlah Data yang ada). Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (0 + 6) / 2 = (6) / 2 = 3. Nilai Data dengan index 3 ialah 4. Nilai Data = 4. Selanjutnya, lakukan pengecekan. Karena Nilai Data < Data yang dicari (4 < 12) maka, untuk iterasi berikutnya Index_Awal = Index_Tengah + 1. Untuk contoh diatas maka, Index_Awal = 3 + 1 = 4. Ingat !!! Peraturan yang sudah saya uraikan diatas.
- Untuk iterasi ke-2, Index_Awal = 4 (Karena pada iterasi sebelumnya, Nilai Data < Data yang dicari). Index_Akhir = 6(Tetap tak ada perubahan). Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (4 + 6) / 2 = (10) / 2 = 5. Nilai Data dengan index 5 ialah 12. Lakukan pengecekan, Data ke-n = 12 dan Data yang dicari = 12 maka, Data yang dicari ditemukan.
- Proses pencarian berhenti dan tampilkan output “Data yang dicari ditemukan pada iterasi ke-2”.
Kebetulan untuk diatas, pencariannya dilakukan terhadap Data yang memang ada. Bagaimana, kalau Data yang tidak ada. Ok, saya lanjutkan lagi ya dengan 1 contoh kasus terakhir terhadap pencarian data yang memang benar – benar tidak ada. Masih dengan Data yang sama.
Data : 12 9 3 4 20 1 -5
Data yang dicari : 10
Proses Binnary Searching :
1. Sorting terlebih dahulu Data secara Ascending.
2. Buat tabel berikut.
3. Lakukan proses Binnary Searching. Seperti tabel berikut.
Penjelasan Proses Binnary Searching
- Untuk iterasi ke-1, Index_Awal = 0, Index_Akhir = 6, Index_Tengah = 3 dan Data dengan index 3 ialah 4. Karena, 4 lebih kecil dari 10 (Data ke-n < Data yang dicari) maka, untuk iterasi berikutnya Index_Awal = Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (0 + 6) / 2 = 6 / 2 = 3. Data dengan index 3 ialah bernilai 4. Lakukan pengecekan, karena 4 < 10 (Data ke-n < Data yang dicari) maka, untuk iterasi berikutnya Index_Awal = Index_Tengah + 1.
- Untuk iterasi ke-2, Index_Awal = 4 (Karena, pada iterasi sebelumnya Data ke-n < Data yang dicari), Index_Akhir = 6 (Tetap), Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (4 + 6) / 2 = 10 / 2 = 5. Data dengan index 5 ialah bernilai 12. Lakukan pengecekan, karena 12 > 10 (Data ke-n > Data yang dicari) maka, untuk iterasi berikutnya, Index_Akhir = Index_Tengah – 1.
- Untuk iterasi ke-3, Index_Awal = 4 (Tetap), Index_Akhir = 4 (Karena, pada iterasi sebelumnya Data ke-n > Data yang dicari), Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (4 + 4) / 2 = 8 / 2 = 4. Data dengan index 4 ialah bernilai 9. Lakukan pengecekan, karena 9 < 10 (Data ke-n < Data yang dicari) maka, untuk iterasi berikutnya, Index_Awal = Index_Tengah + 1 → 4 + 1 = 5.
- Untuk iterasi ke-4, Index_Awal = 5 (Karena, pada iterasi sebelumnya Data ke-n < Data yang dicari), Index_Akhir = 4 (Tetap), Index_Tengah = (Index_Awal + Index_Akhir) / 2 = (5 + 4) / 2 = 9 / 2 = 4 (Gunakan sifat integer). Lakukan pengecekan, karena 9 < 10 (Data ke-n < Data yang dicari) maka, untuk iterasi berikutnya, Index_Awal = Index_Tengah + 1 → 4 + 1 = 5.
- Kalau Anda lanjutkan ini secara terus – menerus maka, hasilnya akan tetap sama dan itu menandakan bahwa Data yang Anda cari tidak ditemukan.
- Hentikan proses pencarian, dan cetak output “Data yang dicari tidak ditemukan”.
Berikut ialah source code untuk program Binnary Searching.
Ket : data.length --> method untuk mengetahui nilai panjang dari sebuah array atau banyaknya elemen di dalam array.
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| import java.util.Scanner;/** * * @author Yudi Setiawan * * Binnary Searching. * */public class BinnarySearching{ public static void main(String[] args) { // Objek Scanner Scanner scan = new Scanner(System.in); // Input jumlah Data System.out.print("Masukkan jumlah Data : "); int jlh_data = scan.nextInt(); // Input nilai tiap Data int[] data = new int[jlh_data]; System.out.println(); for(int a = 0; a < jlh_data; a++) { System.out.print("Nilai Data ke-"+(a+1)+" : "); data[a] = scan.nextInt(); } // Urutkan Data secara Ascending setSortAsc(data); // Panggil procedure // Tampilkan hasil Sorting System.out.println("\nData Setelah di Urutkan"); System.out.print("Data : "); for(int a = 0; a < jlh_data; a++) System.out.print(data[a]+"\t"); System.out.println(); System.out.print("Index : "); for(int a = 0; a < jlh_data; a++) System.out.print(a+"\t"); // Input nilai yang dicari System.out.print("\n\nMasukkan nilai yang dicari : "); int cari = scan.nextInt(); // Proses Binnary Searching int index_awal = 0, index_akhir = data.length - 1, index_tengah = (index_awal + index_akhir) / 2; int nilai_data = data[index_tengah]; int temp_data = 0; int iterasi = 0, sama = 0; boolean temu = false; System.out.println("\n\nProses Binnary Searching"); System.out.println("\nIterasi\tIndex_Awal\tIndex_Akhir\tIndex_Tengah\tNilai_Data"); while(temu == false) { iterasi++; index_tengah = (index_awal + index_akhir) / 2; System.out.print(iterasi+"\t\t"+index_awal+"\t\t"+index_akhir+"\t\t"+index_tengah+"\t\t"+data[index_tengah]); if(data[index_tengah] == cari) { temu = true; System.out.println(" --> Data ditemukan"); } else if(data[index_tengah] > cari) { index_akhir = index_tengah - 1; System.out.println(" --> "+data[index_tengah]+" > "+cari+" maka, index_akhir = index_tengah - 1"); } else if(data[index_tengah] < cari) { index_awal = index_tengah + 1; System.out.println(" --> "+data[index_tengah]+" < "+cari+" maka, index_awal = index_tengah + 1"); } // Kondisi jika ternyata Data yang dicari tidak ditemukan, maka pasti // akan kejadian nilai Data yang sama secara terus menerus if(temp_data != data[index_tengah]) temp_data = data[index_tengah]; else sama++; // Jika sudah sama sebanyak 3 kali maka, proses pencarian berhenti. if(sama >= 3) break; } if(temu == true) System.out.println("\nData ditemukan pada iterasi ke-"+iterasi); else System.out.println("\nData tidak ditemukan"); } // Procedure untuk mengurutkan Data secara Ascending static void setSortAsc(int[] data) { for(int x = 0; x < data.length; x++) { for(int y = 0; y < data.length - 1; y++) { if(data[y] > data[y+1]) { // Proses Pertukaran data int temp = data[y]; data[y] = data[y+1]; data[y+1] = temp; } } } }} |
Tidak ada komentar:
Posting Komentar