Sebelum kita mempelajari carian Binari, mari kita pelajari:
Apa itu Carian?
Pencarian adalah utiliti yang memungkinkan penggunanya mencari dokumen, fail, media, atau jenis data lain yang disimpan di dalam pangkalan data. Pencarian berfungsi berdasarkan prinsip mudah memadankan kriteria dengan catatan dan memaparkannya kepada pengguna. Dengan cara ini, fungsi carian paling asas berfungsi.
Apa itu Carian Binari?
Pencarian binari adalah jenis algoritma carian lanjutan yang mencari dan mengambil data dari senarai item yang disusun. Prinsip kerja utamanya melibatkan membahagikan data dalam senarai menjadi separuh sehingga nilai yang diperlukan terletak dan dipaparkan kepada pengguna dalam hasil carian. Pencarian binari biasanya dikenali sebagai carian selang setengah atau carian logaritma .
Dalam tutorial algoritma ini, anda akan belajar:
- Apa itu Carian?
- Apa itu Carian Binari?
- Bagaimana Pencarian Binari Berfungsi?
- Contoh Carian Binari
- Mengapa Kita Memerlukan Pencarian Binari?
Bagaimana Pencarian Binari Berfungsi?
Pencarian binari berfungsi dengan cara berikut:
- Proses carian dimulakan dengan mencari elemen tengah dari susunan data yang disusun
- Selepas itu, nilai utama dibandingkan dengan elemen
- Sekiranya nilai kunci lebih kecil daripada elemen tengah, maka carian menganalisis nilai atas ke elemen tengah untuk perbandingan dan pemadanan
- Sekiranya nilai kunci lebih besar daripada elemen tengah maka carian menganalisis nilai yang lebih rendah ke elemen tengah untuk perbandingan dan pemadanan
Contoh Carian Binari
Mari kita lihat contoh kamus. Sekiranya anda perlu mencari kata tertentu, tidak ada yang melalui setiap perkataan secara berurutan tetapi secara rawak mencari perkataan terdekat untuk mencari kata yang diperlukan.
Gambar di atas menggambarkan perkara berikut:
- Anda mempunyai susunan 10 digit, dan elemen 59 perlu dijumpai.
- Semua elemen ditandai dengan indeks dari 0 - 9. Sekarang, tengah array dikira. Untuk melakukannya, anda mengambil nilai kiri dan kanan indeks dan membaginya dengan 2. Hasilnya ialah 4.5, tetapi kami mengambil nilai minimum. Oleh itu bahagian tengahnya adalah 4.
- Algoritma menjatuhkan semua elemen dari tengah (4) ke batas paling rendah kerana 59 lebih besar daripada 24, dan kini susunan dibiarkan dengan 5 elemen sahaja.
- Sekarang, 59 lebih besar daripada 45 dan kurang dari 63. Tengahnya adalah 7. Oleh itu nilai indeks kanan menjadi tengah - 1, yang sama dengan 6, dan nilai indeks kiri tetap sama seperti sebelumnya, iaitu 5.
- Pada ketika ini, anda tahu bahawa 59 datang setelah 45. Oleh itu, indeks kiri, yang merupakan 5, menjadi pertengahan juga.
- Iterasi ini berterusan sehingga array dikurangkan menjadi satu elemen sahaja, atau item yang akan dijumpai menjadi tengah array.
Contoh 2
Mari lihat contoh berikut untuk memahami carian binari berfungsi
- Anda mempunyai pelbagai nilai yang disusun antara 2 hingga 20 dan perlu mencari 18.
- Purata had bawah dan atas adalah (l + r) / 2 = 4. Nilai yang dicari lebih besar daripada pertengahan iaitu 4.
- Nilai array kurang dari pertengahan dijatuhkan dari carian dan nilai lebih besar daripada nilai pertengahan 4 dicari.
- Ini adalah proses pemisah berulang sehingga item sebenar yang hendak dicari dijumpai.
Mengapa Kita Memerlukan Pencarian Binari?
Sebab berikut menjadikan carian binari sebagai pilihan yang lebih baik untuk digunakan sebagai algoritma carian:
- Pencarian binari berfungsi dengan cekap pada data yang disusun tidak kira ukuran data
- Daripada melakukan carian dengan melalui data secara berurutan, algoritma binari mengakses data secara rawak untuk mencari elemen yang diperlukan. Ini menjadikan kitaran carian menjadi lebih pendek dan tepat.
- Pencarian binari melakukan perbandingan data yang disusun berdasarkan prinsip pesanan daripada menggunakan perbandingan persamaan, yang lebih perlahan dan kebanyakannya tidak tepat.
- Selepas setiap kitaran carian, algoritma membahagi ukuran array menjadi separuh maka pada lelaran seterusnya ia hanya akan berfungsi pada separuh array yang tersisa
Ringkasan
- Pencarian adalah utiliti yang membolehkan penggunanya mencari dokumen, fail, dan jenis data lain. Pencarian binari adalah jenis algoritma carian lanjutan yang mencari dan mengambil data dari senarai item yang disusun.
- Pencarian binari biasanya dikenali sebagai carian selang setengah atau carian logaritma
- Ia berfungsi dengan membahagikan susunan menjadi separuh pada setiap lelaran di bawah elemen yang diperlukan.
- Algoritma binari mengambil bahagian tengah array dengan membahagikan jumlah nilai indeks kiri dan kanan dengan 2. Sekarang, algoritma menjatuhkan sama ada unsur bawah atau atas elemen dari tengah array, bergantung pada elemen yang akan dijumpai .
- Algoritma mengakses data secara rawak untuk mencari elemen yang diperlukan. Ini menjadikan kitaran carian menjadi lebih pendek dan tepat.
- Pencarian binari melakukan perbandingan data yang disusun berdasarkan prinsip pesanan daripada menggunakan perbandingan persamaan yang lambat dan tidak tepat.
- Pencarian binari tidak sesuai untuk data yang tidak disusun.