Interpolation Search
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 saya ingin membagi sesuatu yang mungkin bisa bermanfaat, yaitu contoh algoritma, scrip, dan output mengenai interpolation Search.
Algoritma pembuatan interpolation Search :
Dan di bawah ini adalah contoh scrip serta output pembuatan interpolation Search :
Sekian terimakasih atas kunjungan anda, semoga bermanfaat
wassalamu'alaikum wr wb
– 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 saya ingin membagi sesuatu yang mungkin bisa bermanfaat, yaitu contoh algoritma, scrip, dan output mengenai interpolation Search.
Algoritma pembuatan interpolation Search :
- Mulai
- Banyaknya record array (k)
- Nilai awal min=0 ; max=k-1
- Hitung mid= min + ((kunci - k[min]) * (max - min)) /(k[max] – k[min])
- Bandingkan data yang dicari(kunci) dengan data posisi tengah(mid)
- Jika lebih kecil, proses dilanjutkan dengan posisi max = posisi tengah-1
- Jika lebih besar, proses dilanjutkan dengan posisi min=posisi tengah+1
- Jika data posisi tengah(mid) = data yang dicari(kunci) , maka index=mid, selesai
- Jika min<=max dan k[mid]=!kunci, maka ulangi langkah 3
- Jika k[mid]=!kunci, maka index=-1
- selesai
Dan di bawah ini adalah contoh scrip serta output pembuatan interpolation Search :
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
int main() {
int data[5] = {2,3,4,5,6};
int cari_data, posisi, awal, akhir, proses;
bool berhenti = false;
cout<<"Data: ";
for(int x = 0; x<5; x++)
cout<<setw(3)<<data[x];
cout<<endl<<endl;
cout << "Data yang dicari : ";
cin >> cari_data;
awal = 2;
akhir = 5;
proses = 0;
#include <conio.h>
#include <iomanip>
using namespace std;
int main() {
int data[5] = {2,3,4,5,6};
int cari_data, posisi, awal, akhir, proses;
bool berhenti = false;
cout<<"Data: ";
for(int x = 0; x<5; x++)
cout<<setw(3)<<data[x];
cout<<endl<<endl;
cout << "Data yang dicari : ";
cin >> cari_data;
awal = 2;
akhir = 5;
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 indeks ke-" << posisi <<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.\n";
berhenti = true;
}
}
return 0;
}
posisi =
(((cari_data-data[awal])*(akhir-awal))/(data[akhir]-data[awal])+awal);
if(data[posisi] == cari_data) {
cout << "Data " << cari_data << " pada posisi indeks ke-" << posisi <<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.\n";
berhenti = true;
}
}
return 0;
}
Dari sourch code dan output tersebut diatas, dapat kita lihat satu baris yang menunjukkan pemakaian dari fungsi Interpolation Search, kode tersebut adalah (((cari_data-data[awal])*(akhir-awal))/(data[akhir]-data[awal])+awal);.
Sekian terimakasih atas kunjungan anda, semoga bermanfaat
wassalamu'alaikum wr wb
Langganan:
Posting Komentar (Atom)
0 komentar:
Posting Komentar