STRUKTUR DATA

                    INTERPOLATION SEARCH

 

  Hallo semua,terimakasih sudah mampir ke blog saya, pada kesempatan kali ini saya akan memberikan sedikit ilmu tentang "Interpolation Search"yang terdiri dari Teknis/tema,Algoritma,contoh program,dan outpit dari program itu sendiri.

1.Teknis/Tema

Interpolation Search adalah sebuah algoritma atau metode untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci.

Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu. Teknik searching ini dilakukan dengan perkiraan letak data. Contoh ilustrasi: jika kita hendak mencari suatu kata di dalam kamus telepon, misal yang berawalan dengan huruf J, maka  kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 1/3 atau 1/4 dari tebal kamus.

Rumus posisi relatif kunci pencarian dihitung dengan rumus:

- Jika data[posisi] > data yg dicari, high = pos – 1
- Jika data[posisi] < data yg dicari, low = pos + 1

2.Algoritma Interpolation Search

1. Mulai
2. Banyaknya record array (k)
3. Nilai awal min=0 ; max=k-1
4. Hitung mid= min + ((kunci - k[min]) * (max - min)) /(k[max] – k[min])
5. Bandingkan data yang dicari(kunci) dengan data posisi tengah(mid)
6. Jika lebih kecil, proses dilanjutkan dengan posisi max = posisi tengah-1
7. Jika lebih besar, proses dilanjutkan dengan posisi min=posisi tengah+1
8. Jika data posisi tengah(mid) = data yang dicari(kunci) , maka index=mid, selesai
9. Jika min<=max dan k[mid]=!kunci, maka ulangi langkah 3
10. Jika k[mid]=!kunci, maka index=-1
11.  selesai

3.Contoh program

Berikut ini adalah contoh program interpolation search yang dapat saya berikan

 

4.Output
Dan ini adalah hasil output dari program Interpolation Search diatas

 Terimakasih telah berkunjung ke blog saya,sampai bertemu lagi di postingan saya selanjutnya ;)