Algoritma Interpolation Search, Definisi dan Contoh Aplikasinya

55
Algoritma Interpolation Search
Algoritma Interpolation Search

ZONANGOPI.COMInterpolation Search adalah algoritma pencarian yang lebih efisien daripada algoritma Binary dan Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut.

Sama seperti Binary, teknik ini hanya dapat dilakukan pada list yang telah terurut dan berada pada struktur array dan data yang dicari diperkirakan ada di dalam list.

Teknik ini menemukan item dengan memperkirakan seberapa jauh kemungkinan item berada dari posisi saat itu dan pencarian berikutnya. Teknik ini juga dilakukan pada list yang sudah terurut. (Suprapta, 2011).

Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data.

Adapun pseudocode dari algoritma interpolation search adalah sebagai berikut :

Algoritma Interpolation Search

Analisis Algoritma Interpolation Search

Rumus umum Interpolation Search terdapat pada persamaan berikut :

interpolation search

  • Jika K[posisi] > data yg dicari, max = pos – 1
  • Jika K[posisi] < data yg dicari, min = pos + 1

Algoritma pencarian interpolation search dapat dituliskan sebagai berikut:
1. Banyaknya record array (k)
2. Nilai awal min=0 ; max=k-1

interpolation search
4. Bandingkan data yang dicari(kunci) dengan data posisi
5. Jika data posisi = data yang dicari(kunci) , data telah ditemukan dan program selesai,
6. Jika lebih kecil, proses dilanjutkan dengan posisi max = posisi -1
7. Jika lebih besar, proses dilanjutkan dengan posisi min=posisi+1
8. Jika kunci >= K[min] && kunci <=K[max], maka ulangi langkah 3
9. Jika tidak, selesai.

Berikut adalah Flowchart Interpolation Search

 

 

Flowchart interpolation search
Flowchart interpolation search

Untuk melihat penerapan algoritma ini, ada pada artikel saya sebelumnya Kamus Android Kata Serapan Menggunakan Algoritma Interpolation Search dan Fitur Auto Complete Teks

Untuk download apk aplikasi nya bisa di download disini

1 KOMENTAR

LEAVE A REPLY

Please enter your comment!
Please enter your name here