Pencarian Biner vs Pencarian Linier
Pencarian linier, juga dikenal sebagai pencarian sekuensial adalah algoritma pencarian yang paling sederhana. Ini mencari nilai tertentu dalam daftar dengan memeriksa setiap elemen dalam daftar. Pencarian biner juga merupakan metode yang digunakan untuk menemukan nilai tertentu 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 Linier?
Pencarian linier adalah metode pencarian paling sederhana, yang memeriksa setiap elemen dalam daftar secara berurutan hingga menemukan elemen tertentu. 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 dalam urutan. Karena metode ini memeriksa setiap item dalam daftar hingga item yang ditentukan ditemukan, dalam kasus terburuk metode ini akan memeriksa 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 untuk diterapkan.
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 tengah daftar. Jika perbandingan menentukan bahwa kedua elemen sama, metode berhenti dan mengembalikan posisi elemen. Jika elemen yang dicari lebih besar dari elemen tengah, metode akan dimulai lagi hanya dengan menggunakan bagian bawah dari daftar yang diurutkan. Jika elemen yang dicari kurang dari elemen tengah, metode akan dimulai lagi hanya dengan menggunakan bagian atas dari daftar yang 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 Linier?
Meskipun pencarian linier dan pencarian biner adalah metode pencarian, mereka memiliki beberapa perbedaan. Sementara pencarian biner beroperasi pada daftar yang diurutkan, pencarian liner juga dapat beroperasi pada daftar yang tidak disortir. Pengurutan daftar umumnya memiliki kompleksitas kasus rata-rata n log n. pencarian linier sederhana dan mudah diterapkan daripada pencarian biner. Namun, 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 hanya dapat ditemukan di lima dari dua puluh buku.
