Perbedaan antara pencarian biner dan pencarian linier

Pencarian biner vs pencarian linier

Pencarian linier, juga dikenal sebagai pencarian berurutan adalah algoritma pencarian paling sederhana. Ini mencari nilai yang ditentukan dalam daftar dengan memeriksa setiap elemen dalam daftar. Pencarian biner juga merupakan metode yang digunakan untuk menemukan nilai yang ditentukan dalam daftar yang diurutkan. Metode pencarian biner membagi dua elemen yang diperiksa (dalam setiap iterasi), mengurangi waktu yang dibutuhkan untuk menemukan item yang diberikan dalam daftar.

Apa itu pencarian linier?

Pencarian linier adalah metode pencarian paling sederhana, yang memeriksa setiap elemen dalam daftar secara berurutan sampai menemukan elemen yang ditentukan. Input ke metode pencarian linier adalah urutan (seperti array, koleksi atau string) dan item yang perlu dicari. Outputnya benar jika item yang ditentukan berada dalam urutan yang disediakan atau salah jika tidak ada dalam urutan. Karena metode ini memeriksa setiap item dalam daftar sampai item yang ditentukan ditemukan, dalam kasus terburuk akan melalui semua elemen dalam daftar sebelum menemukan elemen yang diperlukan. Kompleksitas pencarian linier adalah O (n). Oleh karena itu dianggap terlalu lambat untuk digunakan saat mencari elemen dalam daftar besar. Tapi ini sangat sederhana dan lebih mudah diterapkan.

Apa itu pencarian biner?

Pencarian biner juga merupakan metode yang digunakan untuk menemukan item yang ditentukan dalam daftar yang diurutkan. Metode ini dimulai dengan membandingkan elemen yang dicari dengan elemen di tengah daftar. Jika perbandingan menentukan bahwa kedua elemen sama dengan metode berhenti dan mengembalikan posisi elemen. Jika elemen yang dicari lebih besar dari elemen tengah, ia memulai metode lagi dengan hanya menggunakan bagian bawah dari daftar yang diurutkan. Jika elemen yang dicari kurang dari elemen tengah, ia memulai metode lagi dengan hanya menggunakan bagian atas daftar yang diurutkan. Jika elemen yang dicari tidak ada dalam daftar, metode ini akan mengembalikan nilai unik yang menunjukkan hal itu. Oleh karena itu metode pencarian biner membagi jumlah jumlah elemen dibandingkan (dalam setiap iterasi), tergantung pada hasil perbandingan. Akibatnya, pencarian biner berjalan dalam waktu logaritmik yang menghasilkan kinerja kasus rata -rata O (log n).

Apa perbedaan antara pencarian biner dan pencarian linier?

Meskipun pencarian linier dan pencarian biner adalah metode pencarian mereka memiliki beberapa perbedaan. Saat pencarian biner beroperasi pada daftar yang diurutkan, pencarian liner juga dapat beroperasi pada daftar yang tidak disortir. Menyortir daftar umumnya memiliki kompleksitas kasus rata -rata n log n. Pencarian linier sederhana dan mudah diimplementasikan daripada pencarian biner. Tapi, pencarian linier terlalu lambat untuk digunakan dengan daftar besar karena kinerja kasus rata -rata O (n). Di sisi lain, pencarian biner dianggap sebagai metode yang lebih efisien yang dapat digunakan dengan daftar besar. Tetapi menerapkan pencarian biner bisa sangat rumit dan sebuah penelitian telah menunjukkan bahwa kode yang akurat untuk pencarian biner dapat ditemukan hanya dalam lima dari dua puluh buku.