Carian Perduaan lwn Carian Linear
Carian linear, juga dikenali sebagai carian berjujukan ialah algoritma carian yang paling mudah. Ia mencari nilai tertentu dalam senarai dengan menyemak setiap elemen dalam senarai. Carian binari juga merupakan kaedah yang digunakan untuk mencari nilai tertentu dalam senarai diisih. Kaedah carian binari mengurangkan separuh bilangan elemen yang diperiksa (dalam setiap lelaran), mengurangkan masa yang diambil untuk mencari item yang diberikan dalam senarai.
Apakah itu Carian Linear?
Carian linear ialah kaedah carian paling mudah, yang menyemak setiap elemen dalam senarai secara berurutan sehingga ia menemui elemen tertentu. Input kepada kaedah carian linear ialah urutan (seperti tatasusunan, koleksi atau rentetan) dan item yang perlu dicari. Output adalah benar jika item yang ditentukan berada dalam urutan yang disediakan atau palsu jika ia tidak berada dalam urutan. Memandangkan kaedah ini menyemak setiap item dalam senarai sehingga item yang ditentukan ditemui, dalam kes paling teruk ia akan melalui semua elemen dalam senarai sebelum ia menemui elemen yang diperlukan. Kerumitan carian linear ialah o(n). Oleh itu ia dianggap terlalu lambat untuk digunakan semasa mencari elemen dalam senarai besar. Tetapi ini sangat mudah dan lebih mudah untuk dilaksanakan.
Apakah itu Carian Binari?
Carian binari juga merupakan kaedah yang digunakan untuk mencari item tertentu dalam senarai diisih. Kaedah ini bermula dengan membandingkan elemen yang dicari dengan elemen di tengah senarai. Jika perbandingan menentukan bahawa kedua-dua elemen adalah sama kaedah berhenti dan mengembalikan kedudukan elemen. Jika elemen yang dicari adalah lebih besar daripada elemen tengah, ia memulakan kaedah sekali lagi menggunakan hanya bahagian bawah senarai yang diisih. Jika elemen yang dicari adalah kurang daripada elemen tengah, ia memulakan kaedah sekali lagi menggunakan hanya bahagian atas senarai yang diisih. Jika elemen yang dicari tiada dalam senarai, kaedah akan mengembalikan nilai unik yang menunjukkan perkara itu. Oleh itu kaedah carian binari mengurangkan separuh bilangan elemen dibandingkan (dalam setiap lelaran), bergantung kepada hasil perbandingan. Akibatnya, carian binari berjalan dalam masa logaritma menghasilkan o(log n) prestasi purata kes.
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 diisih, carian pelapik boleh beroperasi pada senarai tidak diisih juga. Mengisih senarai umumnya mempunyai kerumitan kes purata n log n. carian linear adalah mudah dan mudah untuk dilaksanakan daripada carian binari. Tetapi, carian linear terlalu lambat untuk digunakan dengan senarai besar disebabkan oleh prestasi kes purata o(n). Sebaliknya, carian binari dianggap sebagai kaedah yang lebih cekap yang boleh digunakan dengan senarai yang besar. Tetapi melaksanakan carian binari mungkin agak rumit dan kajian telah menunjukkan bahawa kod tepat untuk carian binari boleh didapati hanya dalam lima daripada dua puluh buku.
