Perbedaan Antara Pencarian Biner Dan Pencarian Linear

Perbedaan Antara Pencarian Biner Dan Pencarian Linear
Perbedaan Antara Pencarian Biner Dan Pencarian Linear

Video: Perbedaan Antara Pencarian Biner Dan Pencarian Linear

Video: Perbedaan Antara Pencarian Biner Dan Pencarian Linear
Video: Perbedaan Pencarian Binary Search dengan Sequential Search 2024, Maret
Anonim

Pencarian Biner vs Pencarian Linear

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 (di 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 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 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. Tetapi ini sangat sederhana dan lebih mudah 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 akan berhenti dan mengembalikan posisi elemen. Jika elemen yang dicari lebih besar dari elemen tengah, itu akan memulai metode lagi hanya dengan menggunakan setengah bagian bawah dari daftar yang diurutkan. Jika elemen yang dicari kurang dari elemen tengah, itu memulai metode lagi hanya menggunakan setengah atas daftar yang diurutkan. Jika elemen yang dicari tidak ada dalam daftar, metode akan mengembalikan nilai unik yang menunjukkan itu. Oleh karena itu metode pencarian biner membagi dua jumlah elemen yang dibandingkan (di setiap iterasi), tergantung pada hasil perbandingan. Karena itu,pencarian biner berjalan dalam waktu logaritmik menghasilkan kinerja kasus rata-rata o (log n).

Apa perbedaan antara Pencarian Biner dan Pencarian Linier?

Meskipun kedua metode pencarian linier dan pencarian biner 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 lebih sederhana dan mudah untuk diterapkan daripada pencarian biner. Namun, penelusuran 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 yang besar. Tetapi menerapkan pencarian biner bisa sangat rumit dan sebuah penelitian menunjukkan bahwa kode akurat untuk pencarian biner hanya dapat ditemukan di lima dari dua puluh buku.

Direkomendasikan: