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 :

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

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.

#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++