PENCARIAN INTERPOLASI

Assalamualaikum wr.wb

Hallo.. sobat kali ini kita akan membuat Algoritma, Flowchart dan Program Pencarian Interpolasi, ini adalah kiriman blog pertama ku dan sebagai tugas STRUKTUR DATA, semoga dapat bermanfaat.. terima kasih..

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.

Ini adalah contoh Algoritma pencarian interpolasi

Program pencarian interpolasi

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

using namespace std;

int main() {
int data[5] = {0,1,2,3,4};
int cari_data, posisi, low, high, proses;
bool berhenti = false;

//tampilkan data awal
cout<<"Data: ";
for(int i = 0; i<5; i++)
cout<<setw(3)<<data[i];
cout<<endl<<endl;

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

//proses pencarian data
low = 0;
high = 4;
proses = 0;do
{
posisi = ((cari_data - data[low]) / (data[high] - data[low]))*(high-low) +  low;
    if (data[posisi] == cari_data){
        proses++;
        break;
}
    if (data[posisi] > cari_data)
        high = posisi-1;
    else if (data[posisi] < cari_data)
        low = posisi + 1;
            }
while(cari_data >= data[low] && cari_data <= data[high]);
    if (proses>0){
    cout << " Data yang dicari ada dalam array\n\n" << cari_data << endl;
    cout << " ===================================\n" << endl;
    }else{
    cout << "data tidak ditemukan dalam array\n" << endl;}

            return(0);
}

Keluaran :