Pengantar Pencarian Biner dan Pencarian Linear
Pencarian linier, juga dikenal sebagai pencarian berurutan merupakan algoritma pencarian yang paling sederhana. Itu 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 Linear?
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 larik, kumpulan, atau string) dan item yang perlu dicari.
Keluarannya benar jika item yang ditentukan ada 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 metode ini akan menelusuri semua elemen dalam daftar sebelum menemukan elemen yang diperlukan.
Kompleksitas pencarian linear adalah o(n). Oleh karena itu dianggap terlalu lambat untuk digunakan saat mencari elemen dalam daftar besar.
Tapi 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 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 setengah 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), bergantung 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 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. Menyortir 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. Tapi mengimplementasikan pencarian biner bisa sangat rumit dan sebuah penelitian telah menunjukkan bahwa kode akurat untuk pencarian biner hanya dapat ditemukan di lima dari dua puluh buku.