Perbezaan antara carian binari dan carian linear

Carian binari vs carian linear

Carian linear, juga dikenali sebagai carian berurutan adalah algoritma carian yang paling mudah. Ia mencari nilai yang ditentukan dalam senarai dengan memeriksa setiap elemen dalam senarai. Carian 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 diambil untuk mencari item yang diberikan dalam senarai.

Apa itu carian linear?

Carian linear adalah kaedah carian yang paling mudah, 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. Output adalah benar jika item yang ditentukan berada dalam urutan yang disediakan atau palsu jika tidak dalam urutan. Oleh kerana kaedah ini memeriksa setiap item dalam senarai sehingga item yang ditentukan dijumpai, dalam kes terburuk, ia akan melalui semua elemen dalam senarai sebelum ia mendapati elemen yang diperlukan. Kerumitan carian linear adalah O (n). Oleh itu ia dianggap terlalu lambat untuk digunakan semasa mencari elemen dalam senarai besar. Tetapi ini sangat mudah dan lebih mudah dilaksanakan.

Apakah carian binari?

Carian Perduaan juga merupakan kaedah yang digunakan untuk mencari item yang ditentukan dalam senarai yang disusun. Kaedah ini bermula dengan membandingkan elemen yang dicari ke unsur -unsur di tengah -tengah senarai. Sekiranya perbandingan menentukan bahawa kedua -dua elemen adalah sama, kaedah berhenti dan mengembalikan kedudukan elemen. Sekiranya elemen yang dicari lebih besar daripada elemen pertengahan, ia memulakan kaedah sekali lagi menggunakan hanya separuh bahagian bawah senarai yang disusun. Sekiranya elemen yang dicari kurang daripada elemen pertengahan, ia memulakan kaedah sekali lagi dengan hanya menggunakan separuh bahagian atas senarai yang disusun. Sekiranya elemen yang dicari tidak berada dalam senarai, kaedah itu akan mengembalikan nilai unik yang menunjukkan bahawa. Oleh itu, kaedah carian binari mengurangkan bilangan elemen berbanding (dalam setiap lelaran), bergantung kepada hasil perbandingan. Oleh itu, carian binari berjalan dalam masa logaritma yang mengakibatkan prestasi kes purata o (log n).

Apakah perbezaan antara carian binari dan carian linear?

Walaupun kedua -dua carian linear dan carian binari mencari kaedah mereka mempunyai beberapa perbezaan. Walaupun carian binari beroperasi pada senarai yang disusun, carian pelapik boleh beroperasi pada senarai yang tidak disusun. Menyusun senarai secara amnya mempunyai kerumitan kes purata n log n. Pencarian linear adalah mudah dan mudah untuk dilaksanakan daripada carian binari. Tetapi, carian linear terlalu lambat untuk digunakan dengan senarai besar kerana prestasi kes O (n). Sebaliknya, carian binari dianggap sebagai kaedah yang lebih efisien yang boleh digunakan dengan senarai besar. Tetapi melaksanakan carian binari mungkin agak rumit dan kajian telah menunjukkan bahawa kod yang tepat untuk carian binari dapat dijumpai hanya lima dari dua puluh buku.