PENCARIAN INTERPOLASI (INTERPOLATION SEARCH)

INTERPOLATION SEARCH

Adalah algoritma pencarian yang mirip seperti binary search, karena sebelum pencarian dilakukan pengurutan terlebuh dahulu. Keuntungan dari interpolation sort adalah, lebih cepat dalam pencarian.  Kerugiannya adalah algoritma ini hanya bisa digunakan pada data yang terurut.

Konsep pencarian interpolation search adalah seperti pada pencarian dalam kamus. Jika kita ingin mencari kata dengan huruf depan S, maka kita tidak perlu mencarinya dari data awal namun dapat dicari langsing pada 2/3 atau 3/4 jumlah data.

interpolation sort, dirumuskan dengan :

    POSISI = keyword-data[low])*(high-low)/(data[high]-data[low])+low

Jika data[posisi] > keyword, high = posisi - 1

Jika data[posisi] < keyword, low  = posisi + 1 

berikut adalah Algoritma dari interpolation search,

ALGORITMA INTERPOLATION SORT

1.  Masukan Data. 
2. Urutkan setiap elemen data dari ter-rendah ke ter-tinggi 
3.  Didapatkan data   Ter-rendah  (LOW)  = 0

                                                Ter-tinggi  (HIGH) = n 
4. Ketika LOW <= HIGH, lakukan
5. POSISI == keyword-data[low])*(high-low)/(data[high]-data[low])+low  
6. Jika data kunci sama dengan data[POSISI] 
7. Maka data ditemukan di index-n 
8. Namun jika data kunci lebih dari data[POSISI],         

    Maka lakukan LOW == POSISI +1 
   9. Namun jika data yang dicar / kunci lebih kecil dari data perhitungan   /data[POSISI], 

    Maka lakukan HIGH== POSISI – 1 
   10.Jika tidak, maka data tidak ditemukan.

     berikut adalah flowchart dari interpolation search,

    FLOWCHART INTERPOLATION SORT

 


berikut contoh kode program interpolation search,

#include <iostream>
#include <conio.h>
#include <iomanip>

using namespace std;

int main()
{
    int data[100];
    int n;
    int keyword, posisi, low, high, proses;
    bool berhenti = false;

    cout << "Masukan jumlah data : " ; cin >> n;
    cout << "INPUT DATA : " << endl;
    for (int i=0; i<n; i++)
    {
        cin >> data[i];
    }
    cout << "Data : ";
    for (int i=0; i<n; i++)
        cout << setw(3) << data[i];
        cout << endl << endl;

    cout << "Data yang dicari : ";
    cin >> keyword;

    low = 0;
    high = n-1;
    proses = 0;

    while(berhenti != true)
    {
        proses++;
        posisi = (((keyword-data[low])*(high-low))/(data[high]-data[low])+low);

    if(data[posisi] == keyword)
        {
            cout << "Data " << keyword << " pada posisi indeks ke-" << posisi <<endl;
            cout << "Proses pencarian sebanyak " << proses <<endl;
            berhenti = true;
        }
    else if(data[posisi] < keyword)
        {
            low = posisi + 1;
        }
    else
        {
            cout << "Data yang anda cari tidak ditemukan.\n";
    berhenti = true;
        }
    }
     return 0;
}



OUTPUT PROGRAM