Simple Search & Binary Search
date
Mar 25, 2024
slug
simple-search-dan-binary-search
status
Published
tags
Algoritma dan Struktur Data
summary
Saya ingin mengawali tulisan ini dengan sebuah contoh, suatu ketika Kamu sedang mencari sebuah kata pada kamus, kata tersebut diawali dengan huruf K, mungkin kamu bisa mencari kata tersebut dari halaman pertama buku lalu membalikan selembar demi selembar sampai kamu mendapat huruf k, tetapi karena kamu tau bahka kamus memiliki urutan kata yang tersetruktur maka akan lebih efektif jika kamu membuka halaman tengah kamus tersebut karena kamu tahu bahwa kalimat dengan awalan huruf K berada pada halaman tengah kamus,
type
Post
Saya ingin mengawali tulisan ini dengan sebuah contoh, suatu ketika kamu sedang mencari sebuah kata pada kamus, kata tersebut diawali dengan huruf K, mungkin kamu bisa mencari kata tersebut dari halaman pertama kamus lalu membuka selembar demi selembar sampai kamu mendapat huruf K, tetapi karena kamu tahu bahwa kamus memiliki urutan kata yang tersetruktur maka akan lebih efektif jika kamu membuka halaman tengah kamus tersebut karena kamu tahu bahwa kalimat dengan awalan huruf K berada pada halaman tengah kamus.
Contoh di atas merubakan salah satu contoh Search Problem, salah satu solusi dari masalah tersebut adalah Binary Search. Binary Search adalah algoritma yang terdiri dari sebuah element yang terurut, seperti contoh kamus di atas yang sudah mengurutkan kata berdasarkan huruf agar kita lebih mudah mencari sebuah kata.
A Simpler Search (Problem) Example
Teman saya sedang memikirkan sebuah angka antara satu sampai seratus, lalu saya mencoba menebak angka tersebut dengan jumlah tebakan sesedikit mungkin. Pada setiap angka yang saya tebak, teman saya akan berkata “Lebih besar”, “Lebih Kecil” atau “Benar”.
Simple Search Way
Kita bisa mulai dengan menebak dari angka satu sampai seratus secara berurutan : 1,2,3,4 …
Cara ini merupakan contoh dari Simple Search, pada setiap tebakan kita hanya akan menghilangkan 1 nomor, semisal angka yang teman saya pikirkan adalah 99, maka saya akan menebak 99 kali.
A Better Way to Search (Binary Search)
Kita bisa mulai dari angka 50 (nilai tengah)
“Terlalu rendah” kata teman saya. Tebakan saya tidak tepat, tetapi saya sudah menghilangkan setengah dari angka, selanjutnya saya akan menebak adalah 75
“Terlalu tinggi” kata teman saya. Tebakan saya masih salah, tetapi saya sudah menghilangkan setengah sisa angka lagi, dengan menggunakan binary search kita akan selalu menebak angka tengah dari seluruh kemungkinan, maka pada setiap tebakan kita akan menghilangkan setengah kemungkinan angka, saya dapat melanjutkan cara tersebut sampai saya berhasil menemukan angka yang sedang dipikirkan teman saya.
Binary Search Performance Explained
Pada 100 kemungkinan angka (seperti contoh) kita dapat menemukan jawabannya hanya dengan 7 kali menebak
berapapun angka yang teman saya pikirkan, saya bisa menebak maksimum 7 langkah, karena saya menghapuskan setengah kemungkinan dalam setiap tebakan.
Pada contoh lainnya, ketika saya sedang mencari kata pada kamus. Kamus tersebut memiliki 240.000 kata, pada kemungkinan terburuk, berapa langkah yang bisa saya temukan?
Jika saya mengunakan Simpel Search, akan membutuhkan 240.000 langkah kemungkinan terburuk jika kata yang sedang saya cari berada di akhir kamus. Tetapi jika saya menggunakan binary search pada setiap langkahnya saya mengurangi setengah kemungkinan sampai saya mendapatkan kata yang saya inginkan. kurang lebih seperti ini:
Pada kasus di atas, binary search hanya membutuhkan 18 langkah untuk menemukan kata yang saya cari.
Secara umum untuk list denga jumlah
n , jika kita mengunakan binary search kita akan membutuhkan log2 n tahapan pada kondisi terburuk. Jika kita mengunakan simpel search maka kita akan membutuhkan n tahapan. CATATAN
Tulisan ini dibuat sebagai catatan pembelajaran saya dari video Algoritma Pemrograman 01 | Simple Search & Binary Search | Kuliah Online