Perbezaan Antara Pencarian Perduaan Dan Pencarian Linear

2024 Pengarang: Mildred Bawerman | [email protected]. Diubah suai terakhir: 2023-12-16 08:40

Carian Perduaan vs Carian Linear

Pencarian linear, juga dikenali sebagai carian berurutan adalah algoritma carian termudah. Ia mencari nilai yang ditentukan dalam senarai dengan memeriksa setiap elemen dalam senarai. Pencarian binari juga merupakan kaedah yang digunakan untuk mencari nilai yang ditentukan dalam senarai yang disusun. Kaedah carian binari mengurangkan bilangan elemen yang diperiksa (dalam setiap lelaran), mengurangkan masa yang diperlukan untuk mencari item yang diberikan dalam senarai.

Apa itu Carian Linear?

Pencarian linier adalah kaedah pencarian termudah, yang memeriksa setiap elemen dalam senarai secara berurutan sehingga ia menemui elemen yang ditentukan. Input ke kaedah carian linear adalah urutan (seperti array, koleksi atau rentetan) dan item yang perlu dicari. Keluarannya benar jika item yang ditentukan berada dalam urutan yang disediakan atau salah jika tidak mengikut urutan. Oleh kerana kaedah ini memeriksa setiap item dalam senarai sehingga item yang ditentukan dijumpai, dalam keadaan terburuk ia akan melalui semua elemen dalam senarai sebelum menemui elemen yang diperlukan. Kerumitan carian linear adalah o (n). Oleh itu ia dianggap terlalu lambat untuk digunakan ketika mencari elemen dalam senarai besar. Tetapi ini sangat mudah dan senang dilaksanakan.

Apa itu Carian Binari?

Pencarian binari juga merupakan kaedah yang digunakan untuk mencari item tertentu dalam senarai yang disusun. Kaedah ini dimulakan dengan membandingkan elemen yang dicari dengan elemen di tengah-tengah senarai. Sekiranya perbandingan menentukan bahawa kedua-dua elemen itu sama kaedah berhenti dan mengembalikan kedudukan elemen. Sekiranya elemen yang dicari lebih besar daripada elemen tengah, ia memulakan kaedah sekali lagi hanya menggunakan separuh bawah senarai yang disusun. Sekiranya elemen yang dicari kurang dari elemen tengah, ia memulakan kaedah sekali lagi hanya menggunakan separuh bahagian atas senarai yang disusun. Sekiranya elemen yang dicari tidak ada dalam senarai, kaedah akan mengembalikan nilai unik yang menunjukkan bahawa. Oleh itu, kaedah carian binari mengurangkan bilangan elemen yang dibandingkan (dalam setiap lelaran), bergantung pada hasil perbandingan. Oleh itu,carian binari dijalankan dalam masa logaritmik yang menghasilkan prestasi kes purata o (log n).

Apakah perbezaan antara Carian Binari dan Carian Linear?

Walaupun kedua-dua carian linear dan carian binari adalah kaedah carian, mereka mempunyai beberapa perbezaan. Walaupun carian binari beroperasi pada senarai yang disusun, carian pelapik juga dapat dijalankan pada senarai yang tidak disusun. Menyusun senarai secara amnya mempunyai kerumitan kes rata-rata n log n. carian linear mudah dan senang dilaksanakan berbanding carian binari. Tetapi, carian linear terlalu perlahan untuk digunakan dengan senarai besar kerana prestasi kes rata-rata o (n). Sebaliknya, carian binari dianggap kaedah yang lebih cekap yang dapat digunakan dengan senarai besar. Tetapi melaksanakan carian binari agak sukar dan satu kajian menunjukkan bahawa kod tepat untuk carian binari hanya terdapat dalam lima daripada dua puluh buku.