Pencarian Interpolasi (interpolation searching)

Pencarian Interpolasi (interpolation searching)

Proses pencarian interpolasi (interpolation search) hampir sama dengan proses pencarian dibinary search, dimana pencarian juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search data dibagi menjadi dua bagian tiap prosesnya. Contoh pencarian dengan metode ini misalnya pencarian nomer telpon pada daftar phonebook. Misalnya nama data yang dicari berawalan huruf F, maka pencariannya tidak akan dilakukan dari awal, namun langsung membuka 2/3 atau 3/4 dari tebal buku. Jadi, data yang dicari relatif terhadap jumlah data.

Secara umum jika dirumuskan, posisi kunci pencarian interpolasi relatif ini adalah:

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

Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu yang
dilakukan dengan perkiraan letak data.

Algoritma

 

Flowchart 

 

Program pencarian interpolasi

#include <iostream> 
#include <conio.h> 
#include <iomanip>
 
using namespace std; 
int main() 
{ 
    int data[7], x;
    int cari_data, posisi, awal, akhir, proses;
    bool berhenti = false;
   
    cout<<"Masukkan Data =\n";
    for (x=0; x<7; x++)
    {
        cin>>data[x];
    }
   
    cout<<"Data: ";
    for(int x = 0; x<7; x++)
    cout<<setw(3)<<data[x];
    cout<<endl<<endl;

    cout << "Data Yang ingin dicari : ";
    cin >> cari_data;
   
    awal = 0;
    akhir = 6;
    proses = 0;
    while(berhenti != true)
     {
      proses++;
      posisi = (((cari_data-data[awal])*(akhir-awal))/(data[akhir]-data[awal])+awal);
      if(data[posisi] == cari_data) {
         cout << "Data " << cari_data << " pada posisi " << posisi <<endl;
         cout << "Proses pencaharian sebanyak " << proses <<endl;
         berhenti = true;
         }
   
      else if(data[posisi] < cari_data) {
          awal = posisi + 1;
          }
        
       else { 
         cout << "Data " << cari_data << " Tidak ditemukan.\n";
         berhenti = true;
           }
    }

getch(); 
return 0; 
}  

output