Algoritma Pencarian Biner dengan CONTOH

Sebelum kita mempelajari pencarian Biner, mari kita pelajari:

Apa itu Pencarian?

Pencarian adalah utilitas yang memungkinkan penggunanya menemukan dokumen, file, media, atau jenis data lain apa pun yang disimpan di dalam database. Pencarian bekerja berdasarkan prinsip sederhana yaitu mencocokkan kriteria dengan catatan dan menampilkannya kepada pengguna. Dengan cara ini, fungsi pencarian paling dasar berfungsi.

Apa itu Pencarian Biner?

Pencarian biner adalah jenis algoritma pencarian lanjutan yang menemukan dan mengambil data dari daftar item yang diurutkan. Prinsip kerja intinya melibatkan pembagian data dalam daftar menjadi setengah hingga nilai yang diperlukan ditemukan dan ditampilkan kepada pengguna di hasil pencarian. Pencarian biner umumnya dikenal sebagai a pencarian setengah interval atau pencarian logaritmik.

Bagaimana Pencarian Biner Bekerja?

Pencarian biner bekerja dengan cara berikut:

• Proses pencarian dimulai dengan menemukan elemen tengah dari array data yang diurutkan
• Setelah itu, nilai kunci dibandingkan dengan elemennya
• Jika nilai kunci lebih kecil dari elemen tengah, maka penelusuran menganalisis nilai atas hingga elemen tengah untuk perbandingan dan pencocokan
• Jika nilai kunci lebih besar dari elemen tengah maka penelusuran menganalisis nilai yang lebih rendah ke elemen tengah untuk perbandingan dan pencocokan

Contoh Pencarian Biner

Mari kita lihat contoh kamus. Jika Anda perlu mencari kata tertentu, tidak ada yang menelusuri setiap kata secara berurutan, tetapi secara acak mencari kata terdekat untuk mencari kata yang dibutuhkan.

Gambar di atas mengilustrasikan hal berikut:

1. Anda memiliki array 10 digit, dan elemen 59 perlu ditemukan.
2. Semua elemen ditandai dengan indeks dari 0 – 9. Sekarang, bagian tengah array dihitung. Untuk melakukannya, Anda mengambil nilai indeks paling kiri dan kanan dan membaginya dengan 2. Hasilnya adalah 4.5, tetapi kita mengambil nilai dasar. Jadi yang tengah adalah 4.
3. Algoritme menghilangkan semua elemen dari batas tengah (4) ke batas terendah karena 59 lebih besar dari 24, dan sekarang array hanya tersisa 5 elemen.
4. Sekarang, 59 lebih besar dari 45 dan kurang dari 63. Bagian tengahnya adalah 7. Maka nilai indeks kanan menjadi tengah – 1, yaitu sama dengan 6, dan nilai indeks kiri tetap sama seperti sebelumnya, yaitu 5.
5. Pada titik ini, Anda tahu bahwa 59 muncul setelah 45. Oleh karena itu, indeks kiri, yaitu 5, juga menjadi pertengahan.
6. Iterasi ini berlanjut hingga array direduksi menjadi hanya satu elemen, atau item yang ditemukan menjadi bagian tengah array.

Contoh 2

Mari kita lihat contoh berikut untuk memahami cara kerja pencarian biner

1. Anda memiliki larik nilai yang diurutkan mulai dari 2 hingga 20 dan perlu menemukan 18.
2. Rata-rata batas bawah dan batas atas adalah (l+r)/2 = 4. Nilai yang dicari lebih besar dari pertengahan yaitu 4.
3. Nilai array yang kurang dari nilai tengah akan dikeluarkan dari pencarian dan nilai yang lebih besar dari nilai tengah 4 akan dicari.
4. Ini adalah proses pembagian yang berulang hingga item sebenarnya yang akan dicari ditemukan.

Mengapa Kita Membutuhkan Pencarian Biner?

Alasan-alasan berikut menjadikan pencarian biner sebagai pilihan yang lebih baik untuk digunakan sebagai algoritma pencarian:

• Pencarian biner bekerja secara efisien pada data yang diurutkan, berapa pun ukuran datanya
• Alih-alih melakukan pencarian dengan menelusuri data secara berurutan, algoritma biner mengakses data secara acak untuk menemukan elemen yang diperlukan. Hal ini membuat siklus pencarian menjadi lebih pendek dan akurat.
• Pencarian biner melakukan perbandingan data yang diurutkan berdasarkan prinsip pengurutan dibandingkan menggunakan perbandingan kesetaraan, yang lebih lambat dan sebagian besar tidak akurat.
• Setelah setiap siklus pencarian, algoritme membagi ukuran larik menjadi setengahnya sehingga pada iterasi berikutnya algoritme hanya akan bekerja pada separuh sisa larik.

Pelajari tutorial kami selanjutnya Pencarian Linier: Python, C++ Example

Kesimpulan

• Pencarian adalah utilitas yang memungkinkan penggunanya mencari dokumen, file, dan jenis data lainnya. Pencarian biner adalah jenis algoritma pencarian lanjutan yang menemukan dan mengambil data dari daftar item yang diurutkan.
• Pencarian biner umumnya dikenal sebagai pencarian setengah interval atau pencarian logaritmik
• Ia bekerja dengan membagi array menjadi dua pada setiap iterasi di bawah elemen yang diperlukan ditemukan.
• algoritma biner mengambil bagian tengah array dengan membagi jumlah nilai indeks kiri dan paling kanan dengan 2. Sekarang, algoritme menghilangkan batas bawah atau batas atas elemen dari tengah array, bergantung pada elemen yang akan ditemukan.
• Algoritma mengakses data secara acak untuk menemukan elemen yang diperlukan. Hal ini membuat siklus pencarian menjadi lebih pendek dan akurat.
• Pencarian biner melakukan perbandingan data yang diurutkan berdasarkan prinsip pengurutan dibandingkan menggunakan perbandingan kesetaraan yang lambat dan tidak akurat.
• Pencarian biner tidak cocok untuk data yang tidak disortir.