Halo sobat dira bagaimana liburannya? pastinya asik dong, baik mari kita kembali belajar tentang binary search.Binary search memiliki fungsi untuk memudahkan kita dalam melakukan pencarian,penambahan, dan juga penghapusan data.
Apa itu Binary Search?
Binary search merupakan sebuah metode pencarian pada array/list yang sudah terurut, kemudian pencarian akan dilakukan dengan membagi dua bagian pada array hingga data yang dicari ditemukan/data sudah tidak bisa dibagi dua lagi.
Studi Kasus
Setelah kita mengetahui definisi dari binary search, mari kita coba selesaikan permasalahan dari Array[] = {2, 82, 45, 78, 10, 20, 7} dan akan mencari data dengan nilai 2 dan 46.
Untuk menyelesaikan permasahan tersebut, kita memerlukan data tersebut dalam keadaan sudah tersortir, coba kita cek terlebih dahulu apakah data dari array diatas sudah tersortir?, jika sudah, maka lakukan binary search, dan jika belum, maka urutkan array terlebih dahulu, cara pengurutan bisa menggunakan salah satu metode pensortingan seperti bubble sort, insertion sort, selection sort, dll.
Setelah array berhasil di sort maka array akan menjadi Array[] = {2, 7, 10, 20, 45, 78, 82}. Setelah itu kita masuk ke dalam logika binary search.
Logika Binary Search:
cari = X
Indeks_cari = -1
Indeks_awal = 0
Indeks_akhir = Array.length — 1
While (indeks_awal <= indeks_akhir) {
tengah = (indeks_awal + indeks_akhir) / 2
If (cari == Array[tengah]) {
Indeks_cari = tengah
} else if (cari < Array[tengah]) {
Indeks_akhir = tengah — 1
} else {
Indeks_awal = tengah + 1
}
}
Untuk penyelesaian pencarian data 2
(2, 7, 10, 20, 45, 78, 82)
Indeks_awal = 0
Indeks_akhir = 6
Cari = 2
Perulangan ke-1
(0 <= 6) // TRUE
tengah = (0 +6) / 2 = 6 /2 = 3
Array[tengah] = Array[3] = 20
Cek
(cari == Array[3]) atau (2 == 20) // FALSE
(cari < Array[3]) atau (2 < 20) // TRUE
Indeks_akhir = tengah — 1 = 3–1 = 2
Perulangan ke-2
(0 <= 2) // TRUE
tengah = (0 +2) / 2 = 2/2 = 1
Array[tengah] = Array[1] = 7
Cek
(cari == Array[1]) atau (2 == 7) // FALSE
(cari < Array[1]) atau (2 < 7) // TRUE
Indeks_akhir = tengah — 1 = 1–1 = 0
Perulangan ke-3
(0 <= 0) // TRUE
tengah = (0 + 0) / 2 = 0/2 = 0
Array[tengah] = Array[0] = 2
Cek
(cari == Array[0]) atau (2 == 2) // TRUE
Indeks_cari = 0
Untuk penyelesaian pencarian data 2 ditemukan di indeks ke-0 dengan 3 perulangan
Sekarang kita cari satu data lagi yaitu 46.
Untuk penyelesaian pencarian data 46
(2, 7, 10, 20, 45, 78, 82)
Indeks_awal = 0
Indeks_akhir = 6
Cari = 46
Perulangan ke-1
(0 <= 6) // TRUE
tengah = (0 +6) / 2 = 6 /2 = 3
Array[tengah] = Array[3] = 20
Cek
(cari == Array[3]) atau (46 == 20) // FALSE
(cari < Array[3]) atau (46 < 20) // FALSE
Masuk ke Else
Indeks_awal = tengah + 1 = 3 + 1 = 4
Perulangan ke-2
(4 <= 6) // TRUE
tengah = (4 +6) / 2 = 10/2 = 5
Array[tengah] = Array[5] = 78
Cek
(cari == Array[5]) atau (46 == 78) // FALSE
(cari < Array[5]) atau (46 < 78) // TRUE
Indeks_akhir = tengah — 1 = 5–1 = 4
Perulangan ke-3
(4 <= 4) // TRUE
tengah = (4 + 4) / 2 = 8/2 = 4
Array[tengah] = Array[4] = 45
Cek
(cari == Array[4]) atau (46 == 45) // FALSE
(cari < Array[4]) atau (46 < 45)// FALSE
Masuk Else
Indeks_awal = tengah + 1 = 4 + 1 = 5
Perulangan ke-4
(indeks_awal <= indeks_akhir) atau (5 <= 4) // FALSE
Perulangan berhenti
Jadi, untuk penyelesaian pencarian data 46 tidak ada dan perulangan dilakukan selama 4 kali, dan berhenti karena indeks_awal lebih besar dari indeks_akhir.
Sekian Terimakasih, nantikan artikel-artikel kami yaa :)
