Al Hasna Sadira

Assalamu'alaykum Wr. Wb

Alhamdulillah kali ini kita masih bertemu dalam keadaan penuh nikmat, nikmat sehat, iman, dan Islam..
Kali ini saya akan sedikit memberikan contoh Interpolation Search atau yang sering disebut pencarian interpolasi. Pencarian interpolasi hampir sama dengan pencarian biner (binary search). Jika dalam pencarian biner data dibagi menjadi dua bagian, maka dalam pencarian interpolasi seperti mencari dalam buku telepon. Karena Interpolation Search adalah sebuah algoritma atau metode untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci. Metode ini didasari pada proses pencarian nomor telepon pada buku telepon yang mana manusia mencari melalui dengan nilai kunci yang terdapat pada buku. Teknik searching ini dilakukan dengan perkiraan letak data.

Rumus interpolation search:
                    Posisi = ( kunci – data[low] / data[high] – data[low] ) * ( high – low ) + low

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

Teknis Interpolation Search
1. Data yang dicari dikurangi dengan data awal (data yang ada pada index ke-0)
2. Hasil dari langkah pertama dikalikan dengan hasil dari pengurangan antara data awal dan data akhir yang sudah ditambahkan dengan awal 
3. Hasil dari perkalian langkah no.2 dibagi dengan hasil dari pengurangan antara data awal (data yang ada pada index ke-0) dan data akhir (data pada index terakhir).
4. Setelah hasil ditemukan, hasil di cek.
5. Apabila hasil dan data yang dicari sama, maka data telah ditemukan dan program selesai.
6. Apabila hasil dan data yang dicari berbeda maka langkah yang harus dilakukan adalah membandingkan hasil dan data yang dicari
7. Apabila hasil lebih kecil dari data yang dicari maka index hasil ditambah dengan 1
8. Kemudian kembali lagi ke langkah 1-5
9. Apabila hasil lebih besar dari data yang dicari maka akan ditampilkan output bahwa data tidak ditemukan.

Algoritma Interpolation Search

1. awal <- 0
2. akhir <- banyakDataArray-1
3. cari_data ? (input bilangan)
4. posisi = ((cari_data - data[awal])*(akhir-awal)+awal)/(data[akhir]-data[awal])
5. cari_data == data[posisi] ?
6. Jika sama, data telah ditemukan dan program selesai
7. Jika tidak, Bandingkan :
           Jika (data[posisi] < cari_data)
           awal = posisi + 1;
8. lakukan langkah 4,5
9. Jika data[posisi] > cari_data, tampilkan data tidak ditemukan, program selesai 


Contoh Program Interpolation Search