Interpolation Search in Java

Dalam postingan kali ini, saya akan menerangkan secara sederhana tentang Interpolation Search(Pencarian interpolasi).

Pertama, apa itu pencarian Interpolasi?

Interpolation 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 baik menaik maupun menurun.

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.

Rumus umum Interpolation Search
terdapat pada persamaan sebagai berikut :

Cara kerja metode pencarian interpolasi
dapat disimulasikan sebagai berikut, dimisalkan memiliki data terurut seperti di bawah ini:

Pencarian 1:
Data yang dicari = 60

• Kunci Pencarian ? 60
• Min=0, Max=7
• Posisi = (60 - 25) / (96 - 25) * (7 - 0) + 0 = 3,45 = [3]
• Kunci[3] < data yang dicari (60),
• min=posisi+1 = 3 + 1 = [4], Ulangi perhitungan
• Min=4, Max=7
• Posisi = (56 - 25) / (96 - 56) * (7 - 4) + 4 = 6,32 = [6]
• Kunci[6] adalah 88 yang lebih besar dari kunci yang dicari dicari (56). Sehingga data tidak ditemukan.

Pencarian 2:
Data yang dicari = 41

• Kunci Pencarian ? 41
• Min=0, Max=7
• Posisi = (41 – 25) / (96 – 25) * (7 – 0) + 0 = 1,57 = [1]
• Kunci[3] < data yang dicari (41),
• min=posisi+1 = 1 + 1 = [2], Ulangi perhitungan
• Min=2, Max=7
• Posisi = (41 – 41) / (96 – 41) * (7 – 2) + 2 = 2 = [2]
• Kunci[2] adalah 41 dan data yang dicari adalah 41 sehingga data ditemukan.

Algoritma Interpolation Search
(singkatan merujuk ke rumus umum interpolation)

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

Flowchar Interpolation
Berikut gambaran flowchart dari pencarian Interpolation.

Implementasi di Java
Dan berikut adalah source code bagaimana interpolation diimplementasikan dalam Java :

public int interpolationSearch(int[] contohArray, int Cari){

  int low = 0;

  int high = contohArray.length - 1;

  int mid;

  while (contohArray[low] <= Cari && contohArray[high] >= Cari) {

   mid = low +

         ((Cari - contohArray[low]) * (high - low))

         (contohArray[high] - contohArray[low]);   

   if (contohArray[mid] < Cari)

    low = mid + 1;

   else if (contohArray[mid] > Cari)

    high = mid - 1;

   else

    return mid;

  }

  if (contohArray[low] == Cari)

   return low;

  else

   return -1;

 }

Ringkasan dari penjelasan diatas, proses pencarian interpolation hampir mirip dengan proses pencarian kata dikamus, yaitu kita mencari data yang dimaksud dengan cara memperkirakan letak datanya.