Perbezaan utama antara carian linear dan carian binari ialah carian binari memerlukan sedikit masa untuk mencari elemen dari senarai unsur disusun. Oleh itu, disimpulkan bahawa kecekapan kaedah carian binari adalah lebih besar daripada carian linear.
Satu lagi perbezaan antara keduanya adalah bahawa terdapat prasyarat untuk pencarian binari, iaitu unsur-unsur mesti disusun semasa dalam pencarian linier tidak ada prasyarat seperti itu. Walaupun kedua-dua kaedah carian menggunakan teknik yang berbeza yang dibincangkan di bawah.
Carta Perbandingan
| Asas untuk perbandingan | Carian linear | Carian perduaan |
|---|---|---|
| Kompleks Masa | O (N) | O (log 2 N) |
| Masa kes terbaik | Elemen Pertama O (1) | Pusat Element O (1) |
| Prasyarat untuk pelbagai | Tidak diperlukan | Array mestilah dalam urutan yang disusun |
| Kes yang paling teruk untuk bilangan elemen N | Perbandingan N diperlukan | Dapat disimpulkan selepas hanya perbandingan 2 N |
| Boleh dilaksanakan pada | Senarai Array dan Terkait | Tidak boleh dilaksanakan secara langsung pada senarai berkaitan |
| Masukkan operasi | Mudah dimasukkan pada akhir senarai | Memerlukan pemprosesan untuk memasukkan di tempat yang sepatutnya untuk mengekalkan senarai disusun. |
| Jenis Algoritma | Bersifat sederhana | Bahagikan dan menakluk secara alamiah |
| Kegunaan | Mudah digunakan dan tidak memerlukan sebarang unsur yang dipesan. | Walau bagaimanapun, algoritma dan unsur-unsur yang rumit perlu diatur dengan teratur. |
| Talian Kod | Kurang | Lebih banyak |
Definisi Carian Linear
Dalam carian linear, setiap elemen dalam array diambil satu demi satu dalam urutan logik dan diperiksa sama ada unsur yang diingini atau tidak. Carian tidak akan berjaya jika semua elemen diakses, dan unsur yang dikehendaki tidak dijumpai. Dalam kes yang paling teruk, bilangan kes purata kita mungkin mengimbas separuh saiz array (n / 2).
Oleh itu, pencarian linear dapat ditakrifkan sebagai teknik yang melintasi array secara berurutan untuk mencari item yang diberikan. Program yang diberikan di bawah menggambarkan pencarian unsur array menggunakan carian.
Kecekapan carian linear
Penggunaan masa atau bilangan perbandingan yang dibuat dalam mencari rekod dalam jadual carian menentukan kecekapan teknik. Sekiranya rekod yang dikehendaki hadir dalam kedudukan pertama jadual carian, maka hanya satu perbandingan dibuat. Apabila rekod yang diingini adalah yang terakhir, maka perbandingan n perlu dibuat. Sekiranya rekod itu dipaparkan di suatu tempat dalam jadual carian, secara purata, bilangan perbandingan akan (n + 1/2). Kecekapan kes terburuk dalam teknik ini ialah O (n) yang bermaksud perintah pelaksanaan.
Program C untuk mencari elemen dengan teknik carian linier.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nMasukkan bilangan elemen:"); scanf ("% d", & n); printf ("Masukkan nombor: \ n"); untuk (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nMasukkan nombor yang hendak dicari:"); scanf ("% d", & item); untuk (i = 0; i = 0) {printf ("\ n% d didapati dalam kedudukan% d:", item, loc + 1); } else {printf ("\ n Item tidak wujud"); } getch (); } Definisi Carian Perduaan
Carian binari adalah algoritma yang sangat berkesan. Teknik carian ini mengambil sedikit masa untuk mencari item yang diberikan dalam perbandingan minimum yang mungkin. Untuk melakukan pencarian binari, pertama, kita perlu menyusun elemen array.
Logik di sebalik teknik ini diberikan di bawah:
- Pertama, temui elemen tengah array.
- Elemen tengah array dibandingkan dengan unsur yang hendak dicari.
Terdapat tiga kes yang mungkin timbul:
- Jika elemen itu adalah unsur yang diperlukan, maka carian itu berjaya.
- Apabila elemen kurang daripada item yang dikehendaki, maka cari separuh pertama array.
- Sekiranya ia lebih besar daripada elemen yang dikehendaki, maka cari dalam separuh kedua array.
Ulangi langkah yang sama sehingga elemen didapati atau ekzos di kawasan carian. Dalam algoritma ini, setiap kawasan carian masa akan dikurangkan. Oleh itu, bilangan perbandingan paling log (N + 1). Akibatnya, ia adalah algoritma yang cekap apabila dibandingkan dengan carian linear, tetapi array perlu disusun sebelum melakukan carian binari.
Program C untuk mencari elemen dengan teknik carian binari.
#include void main () {int i, beg, akhir, tengah, n, cari, array [100]; printf ("Masukkan bilangan elemen \ n"); scanf ("% d", & n); printf ("Masukkan nombor% d \ n", n); untuk (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Masukkan nombor yang hendak dicari \ n"); scanf ("% d", & cari); beg = 0; end = n - 1; tengah = (beg + akhir) / 2; sementara {beg <= akhir} {jika (array [tengah] akhir) printf ("Carian tidak berjaya!% d tidak terdapat dalam senarai. \ n", cari); getch (); } Perbezaan Utama Antara Carian Linear dan Carian Perduaan
- Carian linear bersifat berulang dan menggunakan pendekatan berurutan. Sebaliknya, pencarian binari mengguna pakai pendekatan membahagikan dan menaklukkan.
- Kerumitan masa pencarian linear ialah O (N) manakala carian biner mempunyai O (log 2 N).
- Masa kes terbaik dalam carian linear adalah untuk elemen pertama iaitu, O (1). Sebaliknya, dalam pencarian binari, ia adalah untuk elemen tengah, iaitu, O (1).
- Dalam carian linier, kes terburuk untuk mencari unsur adalah bilangan perbandingan N. Sebaliknya, ia adalah log 2 N jumlah perbandingan untuk carian binari.
- Carian linear boleh dilaksanakan dalam tatasusunan dan juga dalam senarai berkaitan manakala pencarian binari tidak dapat dilaksanakan secara terus pada senarai tertaut.
- Seperti yang kita tahu Perduaan carian memerlukan array disusun yang sebab Ia memerlukan pemprosesan untuk memasukkan di tempat yang tepat untuk mengekalkan senarai disusun. Pada carian linear sebaliknya tidak memerlukan unsur yang disusun, jadi elemen mudah dimasukkan di akhir daftar.
- Carian linear mudah digunakan, dan tidak perlu untuk sebarang elemen yang diperintahkan. Di sisi lain, algoritma carian binari adalah rumit, dan unsur-unsur semestinya diatur secara teratur.
Kesimpulannya
Kedua-dua algoritma carian linear dan binari boleh berguna bergantung kepada aplikasi. Apabila tatasusunan adalah struktur data dan unsur-unsur disusun dalam urutan yang disusun, maka pencarian binari lebih disukai untuk mencari cepat . Jika senarai terkaitan adalah struktur data tanpa mengira bagaimana unsur-unsur disusun, carian linear diguna pakai kerana tidak ada langsung pelaksanaan algoritma carian binari.
Algoritma carian binari yang biasa tidak boleh digunakan untuk senarai tertaut kerana senarai terkaitan adalah sifat yang dinamik dan tidak diketahui di mana elemen tengah sebenarnya ditugaskan. Oleh itu, terdapat keperluan untuk mereka bentuk variasi algoritma carian binari yang boleh berfungsi pada senarai tertaut juga kerana pencarian binari lebih cepat dalam pelaksanaan daripada pencarian linier.
