Sebelum kita mempelajari pencarian Biner, mari pelajari:
Apa itu Pencarian?
Pencarian adalah utilitas yang memungkinkan penggunanya menemukan dokumen, file, media, atau jenis data lainnya yang disimpan di dalam database. Pencarian bekerja berdasarkan prinsip sederhana untuk 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 tingkat lanjut yang menemukan dan mengambil data dari daftar item yang diurutkan. Prinsip kerja intinya melibatkan membagi data dalam daftar menjadi setengahnya hingga nilai yang diperlukan ditemukan dan ditampilkan kepada pengguna di hasil pencarian. Pencarian biner umumnya dikenal sebagai pencarian setengah interval atau pencarian logaritmik .
Dalam tutorial algoritma ini, Anda akan belajar:
- Apa itu Pencarian?
- Apa itu Pencarian Biner?
- Bagaimana Pencarian Biner Bekerja?
- Contoh Pencarian Biner
- Mengapa Kita Membutuhkan Pencarian Biner?
Bagaimana Pencarian Biner Bekerja?
Pencarian biner bekerja dengan cara berikut:
- Proses pencarian dimulai dengan menemukan elemen tengah dari larik data yang diurutkan
- Setelah itu, nilai kunci dibandingkan dengan elemen
- Jika nilai kunci lebih kecil dari elemen tengah, penelusuran menganalisis nilai atas hingga elemen tengah untuk perbandingan dan pencocokan
- Jika nilai kunci lebih besar dari elemen tengah, penelusuran menganalisis nilai yang lebih rendah ke elemen tengah untuk perbandingan dan pencocokan
Contoh Pencarian Biner
Mari kita lihat contoh kamus. Jika Anda perlu menemukan kata tertentu, tidak ada yang menelusuri setiap kata secara berurutan tetapi secara acak menemukan kata terdekat untuk mencari kata yang diperlukan.
Gambar di atas menggambarkan hal berikut:
- Anda memiliki array 10 digit, dan elemen 59 harus ditemukan.
- Semua elemen ditandai dengan indeks dari 0 - 9. Sekarang, tengah array dihitung. Untuk melakukannya, Anda mengambil nilai paling kiri dan kanan dari indeks dan membaginya dengan 2. Hasilnya adalah 4,5, tetapi kami mengambil nilai dasarnya. Oleh karena itu bagian tengahnya adalah 4.
- Algoritme menjatuhkan semua elemen dari tengah (4) ke batas terendah karena 59 lebih besar dari 24, dan sekarang array hanya tersisa 5 elemen.
- Sekarang, 59 lebih besar dari 45 dan kurang dari 63. Yang tengah adalah 7. Maka nilai indeks kanan menjadi tengah - 1, yang sama dengan 6, dan nilai indeks kiri tetap sama seperti sebelumnya, yaitu 5.
- Pada titik ini, Anda tahu bahwa 59 muncul setelah 45. Oleh karena itu, indeks kiri, yaitu 5, juga menjadi pertengahan.
- Iterasi ini berlanjut hingga larik dikurangi menjadi hanya satu elemen, atau item yang akan ditemukan menjadi tengah larik.
Contoh 2
Mari kita lihat contoh berikut untuk memahami cara kerja pencarian biner
- Anda memiliki larik nilai yang diurutkan mulai dari 2 hingga 20 dan perlu menemukan 18.
- Rata-rata batas bawah dan atas adalah (l + r) / 2 = 4. Nilai yang dicari lebih besar dari nilai tengah yaitu 4.
- Nilai larik kurang dari tengah akan dihapus dari pencarian dan nilai yang lebih besar dari nilai tengah 4 dicari.
- Ini adalah proses pembagian berulang sampai item sebenarnya yang akan dicari ditemukan.
Mengapa Kita Membutuhkan Pencarian Biner?
Alasan berikut membuat pencarian biner menjadi pilihan yang lebih baik untuk digunakan sebagai algoritma pencarian:
- Pencarian biner bekerja secara efisien pada data yang diurutkan terlepas dari ukuran datanya
- Alih-alih melakukan pencarian dengan menelusuri data secara berurutan, algoritme biner mengakses data secara acak untuk menemukan elemen yang diperlukan. Ini membuat siklus pencarian lebih pendek dan lebih akurat.
- Pencarian biner melakukan perbandingan data yang diurutkan berdasarkan prinsip pengurutan daripada menggunakan perbandingan kesetaraan, yang lebih lambat dan sebagian besar tidak akurat.
- Setelah setiap siklus pencarian, algoritme membagi ukuran array menjadi dua sehingga pada iterasi berikutnya itu hanya akan berfungsi di setengah sisa array.
Ringkasan
- Pencarian adalah utilitas yang memungkinkan penggunanya mencari dokumen, file, dan jenis data lainnya. Pencarian biner adalah jenis algoritma pencarian tingkat lanjut 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 dibutuhkan ditemukan.
- Algoritme biner mengambil tengah larik dengan membagi jumlah nilai indeks paling kiri dan paling kanan dengan 2. Sekarang, algoritme menjatuhkan batas bawah atau atas elemen dari tengah larik, bergantung pada elemen yang akan ditemukan .
- Algoritme mengakses data secara acak untuk menemukan elemen yang diperlukan. Ini membuat siklus pencarian lebih pendek dan lebih akurat.
- Pencarian biner melakukan perbandingan data yang diurutkan berdasarkan prinsip pengurutan daripada menggunakan perbandingan kesetaraan yang lambat dan tidak akurat.
- Pencarian biner tidak cocok untuk data yang tidak diurutkan.