Struktur Data C++

 
 Interpolation Search

·    Pengertian :

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 nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada  2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data.

Algoritma Interpolation Search : 

   1.  Start 

        2. Menentukan index dan isi dari index tersebut .

           0        1        2       3       4       5       6       7       8       9       index

          10      20      30      40      50      60      70      80      90      100    value

    3. Menentukan keyword yang akan dicari.

        Keyword = 50

        Keyword = 25 

    4. Memasukkanya pada rumus Interpolasi.

     5. Jika hasilnya benar sesuai dengan perhitungan menggunakan rumus interpolasi  maka pencarian akan berhenti karena keyword telah ditemukan tetapi jika hasil berbeda dengan posisi yang ada pada rumus maka data tersebut tidak ditemukan pada data yang ada.

Posisi atau index ke 4 memiliki value 50, berarti keyword yang di cari di temukan di index    ke – 4 yang terdapat dalam data.

Posisi atau index ke 2 memiliki value 20 sedangkan keyword yang di cari adalah 25 maka, keyword 25 tidak terdapat dalam data yang ada.

      6. Finish. 

 Contoh Program : 

#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

int main ()
{
    int data[100];
    int cari_data, posisi, awal, akhir, proses,n;
    bool berhenti = false;

    cout<<"\t\t\t\tINTERPOLATION SEARCH"<<endl<<endl;
    cout<<"Masukan Jumlah Data : "; cin>>n; cout<<endl;
    for(int x=0; x<n; x++)
        {cout<<"Data ke-"<<x+1<<": \t"; cin>>data[x];}
    cout<<"Data awal: ";
    for(int x = 0; x<n; x++)
    cout<<setw(3)<<data[x];
    cout<<endl<<endl;
    cout<<"Data Yang Ingin Anda Cari : "; cin>>cari_data;
    awal = 0; akhir =n; 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 index ke- "<<posisi<<endl;
                    cout<<"=> Data yang di cari di mulai dari index ke 0 <= "<<endl;
                    cout<<"Proses pencarian sebanyak : "<<proses<< endl; berhenti = true;
                }
            else if(data[posisi]<cari_data)
                {awal=posisi+1;}
            else{
                cout<<"Data "<<cari_data<<" Tidak Ditemukan !!!"; berhenti=true;
                }
        }
    return 0;
}

     Coding :

 

 

Output : 

 




by :

Dwi Ani Sulis Setyaningsih

Pend. Teknik Informatika