Bahasa C : Searching, Interpolation Search

 

Pengertian

Proses pencarian data ini hampir sama dengan proses pencarian binary search, pencarian ini juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search kita membagi data menjadi 2 bagian tiap prosesnya, pada interpolation search kita akan membagi data menurut rumus sebagai berikut:

Posisi = ( kunci – data[low] / data[high] – data[low] ) * ( high – low ) + low

Singkatnya proses pencarian interpolation search hampir mirip dengan proses pencarian kata dikamus, yaitu kita mencari data yang dimaksud dengan cara memperkirakan letak data

Contoh Programnya

#include<stdio.h>
int main()
{
  //deklarasi variable
  int A[10], i,j,k,tkr,low,high,pos,tm;
  //proses penginputan data
  for(i=0;i<10;i++)
  {
    printf("data ke-%d:",i+1);
    scanf("%d",&A[i]);
  }
  //Input data yang akan dicari
  printf("Masukkan data yang akan anda cari:");
  scanf("%d",&k);
  //proses pengurutan data
  for(i=0;i<10;i++)
  {
    for(j=i+1;j<10;j++)
    {
        if (A[i]>A[j])
        {
            tkr=A[i];
            A[i]=A[j];
            A[j]=tkr;
        }
    }
  }
  //proses pencarian data
  tm=0;
  high=9;
  low=0;
  do
  {
      pos = ((k - A[low]) / (A[high] - A[low]))*(high-low) + low;
      if (A[pos] == k)
        {
            tm++;
            break;
        }
      if (A[pos] > k)
      high = pos-1;
            else
      if (A[pos] < k)
      low = pos + 1;
  }
  while(k >= A[low] && k <= A[high]);
  if (tm>0)
  {
     printf("data %d yang dicari ada dalam array\n",k);
  }
  //jika tidak ditemukan
  else
  {
     printf("data tidak ditemukan dalam array\n");
  }
 getch();
 return 1;
}

Hasilnya ..