Perbedaan utama antara pencarian linear dan pencarian biner adalah bahwa pencarian biner membutuhkan waktu lebih sedikit untuk mencari elemen dari daftar elemen yang diurutkan. Jadi disimpulkan bahwa efisiensi metode pencarian biner lebih besar dari pencarian linear.
Perbedaan lain antara keduanya adalah bahwa ada prasyarat untuk pencarian biner, yaitu elemen harus diurutkan sementara dalam pencarian linear tidak ada prasyarat seperti itu. Meskipun kedua metode pencarian menggunakan teknik yang berbeda yang dibahas di bawah ini.
Grafik perbandingan
| Dasar untuk perbandingan | Pencarian linear | Pencarian biner |
|---|---|---|
| Kompleksitas Waktu | DI) | O (log 2 N) |
| Waktu kasus terbaik | Elemen Pertama O (1) | Elemen Tengah O (1) |
| Prasyarat untuk sebuah array | Tidak diperlukan | Array harus dalam urutan |
| Kasus terburuk untuk sejumlah elemen | Diperlukan N perbandingan | Dapat menyimpulkan setelah hanya mencatat perbandingan 2 N |
| Dapat diimplementasikan pada | Array dan daftar Linked | Tidak dapat langsung diterapkan pada daftar tertaut |
| Masukkan operasi | Dimasukkan dengan mudah di akhir daftar | Memerlukan pemrosesan untuk menyisipkan di tempat yang tepat untuk mempertahankan daftar yang diurutkan. |
| Jenis algoritma | Berulang di alam | Membagi dan menaklukkan di alam |
| Kegunaan | Mudah digunakan dan tidak perlu elemen yang dipesan. | Bagaimanapun algoritma dan elemen yang rumit harus diatur secara berurutan. |
| Baris Kode | Kurang | Lebih |
Definisi Pencarian Linear
Dalam pencarian linear, setiap elemen array diambil satu per satu dalam urutan logis dan memeriksa apakah elemen yang diinginkan atau tidak. Pencarian tidak akan berhasil jika semua elemen diakses, dan elemen yang diinginkan tidak ditemukan. Dalam kasus terburuk, jumlah kasus rata-rata yang harus kita pindai setengah dari ukuran array (n / 2).
Oleh karena itu pencarian linear dapat didefinisikan sebagai teknik yang melintasi array secara berurutan untuk menemukan item yang diberikan. Program yang diberikan di bawah ini mengilustrasikan pencarian elemen array menggunakan pencarian.
Efisiensi pencarian linear
Konsumsi waktu atau jumlah perbandingan yang dibuat dalam mencari catatan di tabel pencarian menentukan efisiensi teknik. Jika catatan yang diinginkan ada di posisi pertama tabel pencarian, maka hanya satu perbandingan yang dibuat. Ketika catatan yang diinginkan adalah yang terakhir, maka n perbandingan harus dibuat. Jika catatan ditampilkan di suatu tempat di tabel pencarian, secara rata-rata, jumlah perbandingannya adalah (n + 1/2). Efisiensi kasus terburuk dari teknik ini adalah O (n) berarti urutan eksekusi.
Program C untuk mencari elemen dengan teknik pencarian linear.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nMasukkan jumlah elemen:"); scanf ("% d", & n); printf ("Masukkan angka: \ n"); untuk (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nMasukkan nomor yang akan dicari:"); scanf ("% d", & item); untuk (i = 0; i = 0) {printf ("\ n% d ditemukan di posisi% d:", item, loc + 1); } else {printf ("\ n Item tidak ada"); } getch (); } Definisi Pencarian Biner
Pencarian biner adalah algoritma yang sangat efisien. Teknik pencarian ini menghabiskan lebih sedikit waktu dalam mencari item yang diberikan dalam perbandingan minimum yang mungkin. Untuk melakukan pencarian biner, pertama-tama, kita harus mengurutkan elemen array.
Logika di balik teknik ini diberikan di bawah ini:
- Pertama, temukan elemen tengah array.
- Elemen tengah array dibandingkan dengan elemen yang akan dicari.
Ada tiga kasus yang bisa muncul:
- Jika elemen adalah elemen yang diperlukan, maka pencarian berhasil.
- Ketika elemen kurang dari item yang diinginkan, maka cari hanya setengah dari array.
- Jika lebih besar dari elemen yang diinginkan, maka cari di paruh kedua array.
Ulangi langkah yang sama sampai elemen ditemukan atau habis di area pencarian. Dalam algoritma ini, setiap kali area pencarian berkurang. Oleh karena itu jumlah perbandingan paling banyak adalah log (N +1). Sebagai hasilnya, ini adalah algoritma yang efisien jika dibandingkan dengan pencarian linear, tetapi array harus diurutkan sebelum melakukan pencarian biner.
Program C untuk menemukan elemen dengan teknik pencarian biner.
# include void main () {int i, beg, end, middle, n, search, array [100]; printf ("Masukkan jumlah elemen \ n"); scanf ("% d", & n); printf ("Masukkan% d angka \ n", n); untuk (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Masukkan nomor yang akan dicari \ n"); scanf ("% d", & pencarian); mohon = 0; end = n - 1; tengah = (mohon + end) / 2; while (mohon <= end) {if (array [middle] end) printf ("Pencarian tidak berhasil!% d tidak ada dalam daftar. \ n", cari); getch (); } Perbedaan Kunci Antara Pencarian Linier dan Pencarian Biner
- Pencarian linear bersifat iteratif dan menggunakan pendekatan sekuensial. Di sisi lain, pencarian Binary mengimplementasikan pendekatan divide and conquer.
- Kompleksitas waktu pencarian linear adalah O (N) sementara pencarian biner memiliki O (log 2 N).
- Waktu kasus terbaik dalam pencarian linier adalah untuk elemen pertama yaitu, O (1). Sebagai lawan, dalam pencarian biner, itu untuk elemen tengah, yaitu, O (1).
- Dalam pencarian linier, kasus terburuk untuk pencarian elemen adalah jumlah perbandingan N. Sebaliknya, ini adalah jumlah perbandingan log 2 N untuk pencarian biner.
- Pencarian linier dapat diimplementasikan dalam array serta dalam daftar tertaut sedangkan pencarian biner tidak dapat diimplementasikan langsung pada daftar tertaut.
- Seperti yang kita ketahui pencarian Biner membutuhkan array yang diurutkan yang merupakan alasan. Ini membutuhkan pemrosesan untuk memasukkan di tempat yang tepat untuk mempertahankan daftar yang diurutkan. Sebaliknya pencarian linear tidak memerlukan elemen yang diurutkan, sehingga elemen mudah disisipkan di akhir daftar.
- Pencarian linear mudah digunakan, dan tidak perlu elemen yang dipesan. Di sisi lain, algoritma pencarian Biner bagaimanapun rumit, dan elemen-elemennya harus diatur secara berurutan.
Kesimpulan
Algoritma pencarian linear dan biner dapat berguna tergantung pada aplikasi. Ketika sebuah array adalah struktur data dan elemen-elemen diatur dalam urutan, maka pencarian biner lebih disukai untuk pencarian cepat . Jika daftar tertaut adalah struktur data terlepas dari bagaimana elemen-elemen disusun, pencarian linier diadopsi karena tidak tersedianya implementasi langsung dari algoritma pencarian biner.
Algoritme pencarian Biner tipikal tidak dapat digunakan untuk daftar tertaut karena daftar tertaut bersifat dinamis dan tidak diketahui di mana elemen tengah sebenarnya ditugaskan. Oleh karena itu, ada persyaratan untuk merancang variasi dari algoritma pencarian biner yang dapat bekerja pada daftar tertaut juga karena pencarian biner lebih cepat dalam pelaksanaan daripada pencarian linear.
