Algoritma Pencarian Linear & Biner Dijelaskan

Kemampuan untuk mencari beberapa data merupakan aspek penting dari ilmu komputer. Algoritma pencarian digunakan untuk mencari item tertentu dalam kumpulan data.

Algoritma mengembalikan hasil boolean (benar atau salah) ke kueri penelusuran. Mereka juga dapat dimodifikasi untuk memberikan posisi relatif dari nilai yang ditemukan.

Untuk artikel ini, algoritme akan berkonsentrasi pada penentuan apakah suatu nilai ada.

Algoritma Pencarian Linier

Pencarian linier juga dikenal sebagai pencarian sekuensial. Dalam jenis pencarian ini, setiap nilai dalam daftar dikunjungi satu per satu secara berurutan sambil memeriksa apakah ada nilai yang diinginkan.

Algoritme memeriksa nilai demi nilai hingga menemukan nilai yang Anda cari atau kehabisan nilai untuk dicari. Ketika nilai pencarian habis, itu berarti kueri pencarian Anda tidak ada dalam daftar.

Algoritma pencarian sekuensial mengambil daftar nilai dan item yang diinginkan dalam daftar sebagai parameternya. Hasil pengembalian diinisialisasi sebagai Palsu dan akan berubah menjadi benar ketika nilai yang diinginkan ditemukan.

Lihat implementasi Python di bawah ini sebagai contoh:

def linearSearch (daftar saya, item):

ditemukan = Salah

indeks = 0

while index < len (mylist) dan tidak ditemukan:

jika daftar saya[indeks] == item:

ditemukan = Benar

lain:

indeks = indeks+1

kembali ditemukan

Analisis Algoritma

Skenario kasus terbaik terjadi ketika item yang diinginkan adalah yang pertama dalam daftar. Kasus terburuk terjadi ketika item yang diinginkan adalah yang terakhir dalam daftar (item ke-n). Oleh karena itu, kompleksitas waktu untuk pencarian linier adalah O(n).

Rata-rata skenario kasus pada algoritma di atas adalah n/2.

Terkait: Apa itu Notasi Big-O?

Pencarian Linier yang Dimodifikasi

Penting untuk diketahui bahwa algoritme yang digunakan mengasumsikan bahwa daftar item acak disediakan untuknya. Artinya, item daftar tidak dalam urutan tertentu.

Misalkan item berada dalam urutan tertentu, katakanlah dari terkecil ke terbesar. Ini akan mungkin untuk mencapai beberapa keuntungan dalam perhitungan.

Ambil contoh mencari 19 dalam daftar yang diberikan: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Setelah mencapai 23, menjadi jelas bahwa item yang dicari tidak ada dalam daftar. Oleh karena itu, tidak lagi penting untuk melanjutkan pencarian item daftar lainnya.

Algoritma Pencarian Biner

Anda telah melihat bagaimana daftar yang diurutkan dapat mengurangi perhitungan yang diperlukan. Algoritma pencarian biner mengambil lebih banyak keuntungan dari efisiensi ini yang diperkenalkan oleh daftar terurut.

Algoritme dimulai dengan mengambil nilai tengah dari daftar yang dipesan dan memeriksa apakah itu nilai yang diinginkan. Jika tidak, maka nilainya diperiksa apakah lebih kecil atau lebih besar dari nilai yang diinginkan.

Jika kurang, maka tidak perlu memeriksa bagian bawah daftar. Jika tidak, jika lebih besar, maka pindah ke bagian atas daftar.

Terkait: Apa Itu Rekursi dan Bagaimana Cara Menggunakannya?

Terlepas dari sublist mana pun (kiri atau kanan) yang dipilih, nilai tengah akan ditentukan lagi. Nilai diperiksa lagi jika itu adalah nilai yang diperlukan. Jika tidak, akan diperiksa apakah lebih kecil atau lebih besar dari nilai yang diminta.

Proses ini diulang sampai nilai ditemukan jika ada.

Implementasi Python di bawah ini adalah untuk algoritma pencarian biner.

def binarySearch (daftar saya, item):

rendah = 0

tinggi = len (daftar saya) - 1

ditemukan = Salah

sementara rendah <= tinggi dan tidak ditemukan:

tengah = (rendah + tinggi) // 2

jika daftar saya[pertengahan] == item:

ditemukan = Benar

item elif < daftar saya[pertengahan]:

tinggi = pertengahan - 1

lain:

rendah = menengah + 1

kembali ditemukan

Analisis Algoritma

Skenario kasus terbaik terjadi ketika item yang diinginkan ditemukan sebagai item tengah. Skenario terburuk tidak semudah itu. Ikuti analisa di bawah ini:

Setelah perbandingan pertama, n/2 item akan tersisa. Setelah yang kedua, n/4 item akan tersisa. Setelah yang ketiga, n/8.

Perhatikan bahwa jumlah item terus berkurang separuh hingga mencapai n/2i di mana i adalah jumlah perbandingan. Setelah semua pemisahan, kami hanya memiliki 1 item.

Ini menyiratkan:

n/2i=1

Oleh karena itu, pencarian biner adalah O(log n).

Pindah ke Menyortir

Dalam pencarian biner, kami mempertimbangkan kasus di mana array yang diberikan sudah dipesan. Tapi misalkan Anda memiliki dataset yang tidak berurutan dan Anda ingin melakukan pencarian biner di atasnya. Apa yang akan kamu lakukan?

Jawabannya sederhana: urutkan. Ada sejumlah teknik penyortiran dalam ilmu komputer yang telah diteliti dengan baik. Salah satu teknik yang dapat Anda mulai pelajari adalah algoritme pengurutan pemilihan, sementara kami juga memiliki banyak panduan yang terkait dengan area lain.

Cara Menggunakan Sortir Seleksi

Sortir seleksi agak sulit dipahami untuk pemula, tetapi tidak terlalu menantang setelah Anda menguasainya.

Baca Selanjutnya

Tentang Penulis