Linear search (pencarian berurutan), Dikatakan demikian karena algoritma ini menggunakan strategi langsung dengan membandingkan data secara berurutan (lurus) tanpa menggunakan strategi khusus. Algoritma pencarian data Linear Search tidak mangkus (tidak efisien dan efektif) jika diterapkan pada data yang sangat besar. Contohnya, untuk mencari data sebanyak 4.294.967.296 (4 milyar) memiliki rata-rata perbandingan sebanyak 2 milyar, berbeda dengan Algoritma Binary Search yang hanya membutuhkan perbandingan 32 kali saja.
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.
- Jika data[posisi] > data yg dicari, high = pos – 1
- Jika data[posisi] < data yg dicari, high = pos + 1
Berikut contoh program :
#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;
int pilih_cara, bil[20], data_cari, flag, temp;
char ubah;
void squential (int bil[], int data){ //pencarian dengan squential
flag=0;
int ww;
for(ww=0; ww<20; ww++){
if(bil[ww]==data){
flag=1;//jika data ditemukan, maka flag berubah menjadi 1
break;
}
}
if(flag==1){
cout<<"\nData telah ditemukan!"<<endl;
cout<<"Letak : index ke-"<<ww<<endl;//menampilkan letak data pada index array
cout<<"Ubah nilai? (y/t)";
cin>>ubah;
if(ubah=='Y'||ubah=='y'){ //kondisi untuk mengubah nilai dalam array
cout<<"Ubah dengan nilai? ";
cin>>bil[ww];
cout<<"\n\nDATA BERUBAH!";
}
} else {
cout<<"\nTidak ditemukan data!"<<endl;
cout<<"PENCARIAN SElESAI"<<endl;
}
cout<<"\nData anda : \n"; //menampilkan nilai akhir dari hasil pencarian
for(int qq=0;qq<20; qq++){
cout<<bil[qq]<<", ";
}
}
void binnary(int bil[], int data){ //pencarian dengan binnary search
int awal, tengah, akhir;
awal=0;
akhir=19;
while(awal<=akhir && flag==0){
tengah=(awal+akhir)/2;
if(bil[tengah]==data){
flag=1;// bila data ditemukan, maka flag berubah menjadi 1
break;
}else if(bil[tengah]<data){
awal=tengah+1;
cout<<"Cari kanan\n";
}else {
akhir=tengah-1;
cout<<"Cari kiri\n";
}
}
if(flag==1){
cout<<"\nData telah ditemukan!"<<endl;
cout<<"Letak : index ke-"<<tengah<<endl;//menampilkan letak data pada index array
cout<<"Ubah nilai? (y/t)";
cin>>ubah;
if(ubah=='Y'||ubah=='y'){ //kondisi bila nilai dari array yang ditemukan akan diubah
cout<<"Ubah dengan nilai? ";
cin>>bil[tengah];
cout<<"\n\nDATA BERUBAH!";
}
} else {
cout<<"\nTidak ditemukan data!"<<endl;
cout<<"PENCARIAN SElESAI"<<endl;
}
cout<<"\nData anda : \n"; //menampilkan asil akhir dari suatu array
for(int qq=0;qq<20; qq++){
cout<<bil[qq]<<", ";
}
}
void interpolar(int bil[], int data){ //pencariandengan cara interpolation
int low, high, pos;
float posisi;
low=0;
high=19;
do{
posisi= (float) ((data - bil[low]) / (bil[high] - bil[low]))* (high - low) + low;
pos=floor(posisi);
if(bil[pos]==data){ //kondisibila data yang dicari ditemukan
flag=1;//bila data ditemukan flag berubah menjadi 1
break;
}
if(bil[pos]>data){
high=pos-1;
} else if(bil[pos]<data){
low=pos+1;
}
}while(data>=bil[low]&&data<=bil[high]);
if(flag==1){
cout<<"\nData telah ditemukan!"<<endl;
cout<<"Letak : index ke-"<<pos<<endl;//untuk mengetahui letak index pada array yang telahditemukan
cout<<"Ubah nilai? (y/t)"; //kondisi bila ingin mengganti nilai dari suatu arra
cin>>ubah;
if(ubah=='Y'||ubah=='y'){
cout<<"Ubah dengan nilai? ";
cin>>bil[pos];
cout<<"\n\nDATA BERUBAH!";
}
} else {
cout<<"\nTidak ditemukan data!"<<endl;
cout<<"PENCARIAN SElESAI"<<endl;
}
cout<<"\nData anda : \n"; //menampilkan nilai terakhir dari array
for(int qq=0;qq<20; qq++){
cout<<bil[qq]<<", ";
}
}
void cari(int bil[]){
cout<<"\n\n\t\t\t= =PENCARIAN= ="<<endl;
cout<<"Inputkan nilai yang akan dicari : "; //input nilai yang akan dicari dalam array
cin>>data_cari;
cout<<"\n\nPilih cara pencarian :"<<endl;//pilihan cara pencarian
cout<<"\t1. Squential search"<<endl;
cout<<"\t2. Binnary search"<<endl;
cout<<"\t3. Interpolation Search"<<endl;
cout<<"\(1/2/3) ? ";
cin>>pilih_cara;
system("cls");
switch(pilih_cara){
case 1:
squential(bil,data_cari);
break;
case 2:
binnary(bil,data_cari);
break;
case 3:
interpolar(bil,data_cari);
break;
default:
cout<<"Inputan salah!"<<endl;
cout<<"Exit program"<<endl;
system("pause");
exit(1);
}
}
int main(){
cout<<"\t\t= =PROGRAM SEARCHING DATA= ="<<endl<<endl;
cout<<"Pilih cara input angka : "<<endl;//inputan nilai, dengan cara manual atau random
cout<<"\t1. Manual"<<endl;
cout<<"\t2. Random"<<endl;
cout<<"(1/2) ? ";
cin>>pilih_cara;
switch(pilih_cara){
case 1:
cout<<"Inputkan 20 bilangan : "<<endl; //bila nilai diinpukan secara manual
for(int q=0; q<20;q++){
cout<<"\t> Bilangan ke-"<<q+1<<" : "; cin>>bil[q];
}
break;
case 2:
for(int qq=0;qq<20; qq++) //bila nilai diinputakn secara random
bil[qq]=(rand()%999)+1;
break;
default:
cout<<"Inputan salah!"<<endl;
cout<<"Exit program"<<endl;
system("pause");
exit(1);
}
for(int i=1; i<20;i++){ //data yang telah diinput, di urutkan datanya agar memudahkan dalam proses pencarian
for(int iu=20-1;iu>=1; iu--){
if(bil[iu] < bil[iu-1]){ //data urut secara ascending
temp = bil[iu];
bil[iu]=bil[iu-1];
bil[iu-1]=temp;
}
}
}
cout<<"\nData anda : \n"; //menampilkan data
for(int qq=0; qq<20; qq++){
cout<<bil[qq]<<", ";
}
cari(bil);//memanggil fungsi cari
system("pause");
}
Bisa tracing Dengan objek nomor tlpn menggunakan metode insertion searc
BalasHapus