Perbedaan Antara Pencarian Biner dan Pencarian Linear

Pencarian Biner vs Pencarian Linear

Pencarian linear, juga dikenal sebagai pencarian sekuensial adalah algoritma pencarian paling sederhana. Itu 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 jumlah elemen yang diperiksa (dalam setiap iterasi), mengurangi waktu yang dibutuhkan untuk menemukan item yang diberikan dalam daftar.

Apa itu Pencarian Linear?

Pencarian linear adalah metode pencarian paling sederhana, yang memeriksa setiap elemen dalam daftar secara berurutan hingga 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 dalam urutan yang disediakan atau salah jika tidak dalam urutan. Karena metode ini memeriksa setiap item dalam daftar sampai item yang ditentukan ditemukan, dalam kasus terburuk akan melewati semua elemen dalam daftar sebelum menemukan elemen yang diperlukan. Kompleksitas pencarian linear adalah o (n). Oleh karena itu dianggap terlalu lambat untuk digunakan ketika mencari elemen dalam daftar besar. Tetapi ini sangat sederhana dan lebih mudah diimplementasikan.

Apa itu Pencarian Biner?

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

Apa perbedaan antara Pencarian Biner dan Pencarian Linear?

Meskipun pencarian linear dan pencarian biner adalah metode pencarian, mereka memiliki beberapa perbedaan. Sementara pencarian biner beroperasi pada daftar yang diurutkan, pencarian liner dapat beroperasi pada daftar yang tidak disortir juga. Menyortir daftar umumnya memiliki kerumitan kasus rata-rata n log n. pencarian linear sederhana dan mudah diterapkan daripada pencarian biner. Tapi, pencarian linier terlalu lambat untuk digunakan dengan daftar besar karena kinerja kasus rata-rata. 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.