Interpolation Search dan Contohnya – C++

Posted on by

Interpolation Search adalah sebuah algoritma atau metode untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci. Metode ini didasari pada proses pencarian nomor telepon pada buku telepon yang mana manusia mencari melalui dengan nilai kunci yang terdapat pada buku. Teknik searching ini dilakukan dengan perkiraan letak data. Rumus posisi relatif kunci pencarian dihitung dengan rumus berikut ini :

Rumus Interpolation Search

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

UPDATE 26 Mei 2016
Setelah melihat bahwa peminat dari artikel ini sangat banyak, saya mohon maaf karena link download sebelumnya sudah hilang. Ini saya berikan link download terbaru :

Direct Download

Mirror Download

Oke, sekian pendahuluan mengenai Interpolation Search, sekarang aku ingin membagi sesuatu yang mungkin bisa bermanfaat buat temen – temen yang sedang ngerjakan tugas untuk Implementasi Interpolation Search dengan C++.
Source code dibawah ini adalah contoh implementasi dari satu fungsi yang aku buat tersendiri di luar fungsi main() yang bernilai int, dan bervalue / nilai yang dihasilkan fungsi ini adalah posisi index array dimana tempat / posisi data yang Anda cari pada suatu array / kumpulan data yang sudah ada.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <iostream>
#include <string.h>
using namespace std;
int main(int argc, char *argv[]){
int tempFound = 0;
int kodeBarang[] = {101,102,201,301,401,402,501,601,602,701};
string namaBarang[] = {"Flashdisk Kingston", "Flashdisk Data Traveler", "RAM VGEN",
"VGA ATI RADEON", "Laptop Asus", "Netbook HP", "CD ROM", "Mouse",
"Keyboard", "Monitor LG"};
int stokBarang[] = {5, 7, 8, 9, 2, 3, 4, 6, 4, 5};
string lokasiBarang[] = {"Rak 5B", "Rak AA", "Rak 12D", "Rak B6", "Rak VC7", "Rak AB12",
"Rak G23", "Rak K9", "Rak 5J", "Rak D5"};
int kodeKunci;
cout << "\n\tMasukkan kode barang : "; cin >> kodeKunci;
tempFound = interpolationSearch(kodeBarang, kodeKunci, (sizeof(kodeBarang)/4));
if(tempFound>=0){
cout << "\n\n\tBarang yang Anda cari ditemukan, berikut detailnya : " <<endl;
cout << endl;
cout << "\tNama Barang : " << namaBarang[tempFound] <<endl;
cout << "\tStok Barang : " << stokBarang[tempFound] <<endl;
cout << "\tLokasi : " << lokasiBarang[tempFound] <<endl <<endl;
cout << "\t";
}else{
cout << "\n\n\tMohon maaf, barang yang Anda cari belum ada\n\t" <<endl;
}
system("pause");
return EXIT_SUCCESS;
}
#include <iostream> #include <string.h> using namespace std; int main(int argc, char *argv[]){ int tempFound = 0; int kodeBarang[] = {101,102,201,301,401,402,501,601,602,701}; string namaBarang[] = {"Flashdisk Kingston", "Flashdisk Data Traveler", "RAM VGEN", "VGA ATI RADEON", "Laptop Asus", "Netbook HP", "CD ROM", "Mouse", "Keyboard", "Monitor LG"}; int stokBarang[] = {5, 7, 8, 9, 2, 3, 4, 6, 4, 5}; string lokasiBarang[] = {"Rak 5B", "Rak AA", "Rak 12D", "Rak B6", "Rak VC7", "Rak AB12", "Rak G23", "Rak K9", "Rak 5J", "Rak D5"}; int kodeKunci; cout << "\n\tMasukkan kode barang : "; cin >> kodeKunci; tempFound = interpolationSearch(kodeBarang, kodeKunci, (sizeof(kodeBarang)/4)); if(tempFound>=0){ cout << "\n\n\tBarang yang Anda cari ditemukan, berikut detailnya : " <<endl; cout << endl; cout << "\tNama Barang : " << namaBarang[tempFound] <<endl; cout << "\tStok Barang : " << stokBarang[tempFound] <<endl; cout << "\tLokasi : " << lokasiBarang[tempFound] <<endl <<endl; cout << "\t"; }else{ cout << "\n\n\tMohon maaf, barang yang Anda cari belum ada\n\t" <<endl; } system("pause"); return EXIT_SUCCESS; }
#include <iostream>
#include <string.h>

using namespace std;

int main(int argc, char *argv[]){
    int tempFound = 0;
    int kodeBarang[] = {101,102,201,301,401,402,501,601,602,701};
    string namaBarang[] = {"Flashdisk Kingston", "Flashdisk Data Traveler", "RAM VGEN",
                           "VGA ATI RADEON", "Laptop Asus", "Netbook HP", "CD ROM", "Mouse",
                           "Keyboard", "Monitor LG"};
    int stokBarang[] = {5, 7, 8, 9, 2, 3, 4, 6, 4, 5};
    string lokasiBarang[] = {"Rak 5B", "Rak AA", "Rak 12D", "Rak B6", "Rak VC7", "Rak AB12",
                             "Rak G23", "Rak K9", "Rak 5J", "Rak D5"};
    int kodeKunci;
    cout << "\n\tMasukkan kode barang : "; cin >> kodeKunci;

    tempFound = interpolationSearch(kodeBarang, kodeKunci, (sizeof(kodeBarang)/4));
    if(tempFound>=0){
        cout << "\n\n\tBarang yang Anda cari ditemukan, berikut detailnya : " <<endl;
        cout << endl;
        cout << "\tNama Barang : " << namaBarang[tempFound] <<endl;
        cout << "\tStok Barang : " << stokBarang[tempFound] <<endl;
        cout << "\tLokasi      : " << lokasiBarang[tempFound] <<endl <<endl;
        cout << "\t";
    }else{
        cout << "\n\n\tMohon maaf, barang yang Anda cari belum ada\n\t" <<endl;
    }

    system("pause");
    return EXIT_SUCCESS;
}

Dari source code tersebut diatas, dapat kita lihat satu baris yang menunjukkan pemakaian dari fungsi Interpolation Search yang dibuat diluar fungsi main() c++, kode tersebut adalah tempFound = interpolationSearch(kodeBarang, kodeKunci, (sizeof(kodeBarang)/4));
Untuk source code lengkapnya silahkan download file Tugas Struktur Dataku ini, mengenai Interpolation Search dengan C++

9 thoughts on “Interpolation Search dan Contohnya – C++”

  7. Pingback: Interpolation Searching | Ahmad Rizaqu Muttaqi's webblog

Leave a Reply