Kelebihan dan kekurangan Interpolation Search

Table of Contents Show

2. Jenis-jenis Searching
1. Sequential Search
2. Binary Search
3. Interpolation Search
Referensi :
Video yang berhubungan

InterpolationSearch merupakan sebuah teknik pengembangan dari binary search. Teknik binary search akan selalu memeriksa nilai tengah dari setiap array, sedangkan interpolation search dapat pergi ke lokasi yang berbeda berdasarkan key yang didapat. Jika nilai key lebih dekat ke array yang terakhir, maka teknik interpolation search akan memulai pencarian dari array yang terakhir.Nilai Mid untuk interpolation search di dapat dari :

Misalkan kita memiliki int arr[] = {70, 60, 30, 50, 40,20}, data para int arr harus diurutkan terlebih dahulu menggunakan teknik sorting seperti bubble sort. Sehingga array kita akan menjadi int arr[] = {20,30,40,50,60,70}. Apabila angka yang dicari adalah angka 40, berikut gambaran dari implementasi InterpolationSearch:

1st Cycle:
(20,30,40,50,60,70) find=40 low = 0 high = N-1 mid =((find-arr[low]) / (arr[high]-arr[low]))*(high-low) + low= 0 (arr[mid] == 40) (20,30,40,50,60,70) (20==40) // FALSE

low = mid + 1

*Array di mulai dari index ke 0, maka index ke 3 berisi nilai 50.

2nd Cycle:
(20,30,40,50,60,70) find=40 mid =((find – arr[low]) / (arr[high]-arr[low])) *(high-low) + low = 1 (arr[mid] == 40) (20,30,40,50,60,70) (30==40) // FALSE

low = mid + 1

3rd Cycle:
(20,30,40,50,60,70)

Pada cycle ke 3, looping ini sudah berhenti karena melanggar aturan yang dibuat untuk interpolation search. Pada tahap ini ada kemungkinan data nya sudah ditemukan. Kita tinggal mengcheck apakah array bagian low atau high merupakan nilai yang kita cari atau bukan. Jika data ditemukan, maka program akan keluar dari looping. Jika kita ingin menampilkan index dari data yang dicari, kita tinggal menyimpan index dari array tersebut dan menampilkan nya.

Berikut implementasi dari Binary Search menggunakan Bahasa C:

#include <stdio.h>

int main()

{

int arr[]={20, 30, 40, 50, 60, 70};

int n = sizeof(arr)/sizeof(int);

int index=-1; //index array mulai dari 0, maka di set -1

int find=40;

int mid, low = 0, high = n-1;

while(arr[low] < find && arr[high] > find) {

mid = ((find – arr[low]) / (arr[high] – arr[low])) * (high-low) + low;

if(arr[mid] < find){

low = mid + 1;

}

else if(arr[mid] > find){

high = mid – 1;

}

else{

index=mid;

break;

}

if (arr[low] == find){

index = low;

}

else if(arr[high] == find){

index = high;

}

if(index==-1){

printf(“Data tidak ditemukan\n”);

}

else{

printf(“Data berada pada index ke-%d\n”,index);

}

return 0;

}

Reference:

Paul Deitel & Harvey Deitel. (2016). C how to program : with an introduction to C++. 08. Pearson Education. Hoboken. ISBN: 9780133976892.

Published at : 26 December 2019

Dalam kehidupan sehari-hari sebenarnya kita sering melakukan pencarian data. Sebagai contoh, jika kita menggunakan Kamus untuk mencari kata-kata dalam Bahasa Inggris yang belum diketahui terjemahannya dalam Bahasa Indonesia. Contoh lain saat kita menggunakan buku telepon untuk mencari nomor telepon teman atau kenalan dan masih banyak contoh yang lain.

Pencarian (Searching) merupakan suatu proses yang penting dalam pengelolaan data atau nilai. Proses pencarian adalah menemukan suatu data atau nilai tertentu dalam kumpulan data yang memiliki tipe yang sama baik tipe dasar atau tipe bentuk. Data atau nilai yang dimaksud disini adalah data yang disimpan secara temporer dalam memori utama atau disimpan secara permanen didalam memori sekunder contohnya tape atau disk. Didalam memori utama, struktur penyimpanan data yang umum adalah berupa larik atau tabel (array), sedangkan didalam memori sekunder berupa file atau arsip.

2. Jenis-jenis Searching

Ada beberapa jenis searching :

1. Sequential Search

Sequential Search adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen array dari awal hingga yang paling akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

Berikut ini kelebihan dan kekurangan dari Sequential Search :

Proses pencarian menggunakan Sequential Search cenderung lebih cepat dan efisien untuk jumlah data yang terbatas atau tidak terlalu banyak.
Algoritma yang digunakan juga lebih sederhana atau tidak terlalu rumit.
Kekurangan yang paling mendasar Sequential Search adalah kurang efisien dan kurang cepat untuk mencari suatu data dalam jumlah yang besar

Proses-proses dari Sequential Search :

Pertama data akan melakukan perbandingan satu per satu secara berurutan dalam data dengan data yang akan dicari. Proses pencarian ini akan terjadi sampai data ditemukan atau tidak ditemukan dalam kumpulan data tersebut.
Pencarian ini akan melakukan pengulangan dari data awal hingga data akhir sesuai dengan jumlah datanya.
Jika, data yang dimasukkan sama dengan data yang dicari maka data telah berhasil ditemukan. Tapi, jika pengulangan terjadi dari data awal hingga data akhir dan tidak ada data yang sama. Maka, data tersebut tidak ditemukan.

2. Binary Search

Binary Search adalah suatu metode pencarian suatu data yang ada didalam kumpulan data dimana data-data tersebut sudah berurut. Karena, proses pencarian tidak akan terjadi jika data-data yang berada didalam kumpulan data tersebut tidak berurut. Dalam proses pencarian dengan metode ini data akan dibagi menjadi dua bagian untuk setiap tahap pencariannya.

Berikut kelebihan dan kekurangan dari Binary Search:

Efisien dan lebih cepat jika mencari suatu nilai dalam jumlah data yang besar. Karena data-data tersebut sudah diurutkan terlebih dahulu
Kekurangan Binary Search yang pertama adalah data harus diurutkan terlebih dahulu agar proses pencarian bisa berjalan dengan baik
Kekurangan kedua adalah algoritma Binary Search lebih rumit daripada Sequential Search

Proses-proses Binary Search:

Pengambilan data dimulai dari data awal hingga data yang terakhir sesuai dengan jumlah data
Kedua, mencari data yang berada paling tengah dalam kumpulan data tersebut dengan menggunakan rumus :(posisi awal+posisi akhir)/2
Selanjutnya data yang dicari akan dibandingkan dengan data yang paling tengah, jika nilai data yang dicari lebih besar dari nilai data yang paling tengah maka kumpulan data akan dibagi menjadi dua dan data yang berada diposisi paling tengah menjadi posisi awal pencarian data.
Sebaliknya, jika data yang dicari lebih kecil dengan data yang berada diposisi tengah , maka kumpulan data tersebut dibagi menjadi dua bagian dimana data yang berada diposisi tengah menjadi posisi akhir untuk pencarian data. Jika data yang dicari sama, berarti data sudah ketemu.

3. Interpolation Search

Interpolation Search adalah suatu metode pencarian data yang sudah terurut dengan cara memperkirakan letak data yang berada dalam kumpulan data tersebut. Contoh ilustrasi : jika kita mencari kata dalam KBBI dengan awalan M, kita tidak perlu mencari dari awal kamus. Tapi, kita dapat langsung mencari pada bagian tengah kamus tersebut. Proses Interpolation Search menggunakan rumus:

Posisi = (kunci-data[low]/data[high]-data[low])*(high-low)+low

Singkatnya proses pencarian interpolation search hampir mirip dengan proses pencarian kata dikamus, yaitu kita mencari data yang dimaksud dengan cara memperkirakan letak data.

Referensi :

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

INTERPOLATION SEARCH

Adalah algoritma pencarian yang mirip seperti binary search, karena sebelum pencarian dilakukan pengurutan terlebuh dahulu. Keuntungan dari interpolation sort adalah, lebih cepat dalam pencarian. Kerugiannya adalah algoritma ini hanya bisa digunakan pada data yang terurut.

Konsep pencarian interpolation search adalah seperti pada pencarian dalam kamus. Jika kita ingin mencari kata dengan huruf depan S, maka kita tidak perlu mencarinya dari data awal namun dapat dicari langsing pada 2/3 atau 3/4 jumlah data.

interpolation sort, dirumuskan dengan :

POSISI = keyword-data[low])*(high-low)/(data[high]-data[low])+low

Jika data[posisi] > keyword, high = posisi - 1

Jika data[posisi] < keyword, low = posisi + 1

berikut adalah Algoritma dari interpolation search,

ALGORITMA INTERPOLATION SORT

1. Masukan Data.
2. Urutkan setiap elemen data dari ter-rendah ke ter-tinggi
3. Didapatkan data Ter-rendah (LOW) = 0

Ter-tinggi (HIGH) = n
4. Ketika LOW <= HIGH, lakukan
5. POSISI == keyword-data[low])*(high-low)/(data[high]-data[low])+low
6. Jika data kunci sama dengan data[POSISI]
7. Maka data ditemukan di index-n
8. Namun jika data kunci lebih dari data[POSISI],

Maka lakukan LOW == POSISI +1
9. Namun jika data yang dicar / kunci lebih kecil dari data perhitungan /data[POSISI],

Maka lakukan HIGH== POSISI – 1
10.Jika tidak, maka data tidak ditemukan.

berikut adalah flowchart dari interpolation search,

FLOWCHART INTERPOLATION SORT

berikut contoh kode program interpolation search,

#include <iostream>#include <conio.h>#include <iomanip>using namespace std;int main(){ int data[100]; int n; int keyword, posisi, low, high, proses; bool berhenti = false; cout << "Masukan jumlah data : " ; cin >> n; cout << "INPUT DATA : " << endl; for (int i=0; i<n; i++) { cin >> data[i]; } cout << "Data : "; for (int i=0; i<n; i++) cout << setw(3) << data[i]; cout << endl << endl; cout << "Data yang dicari : "; cin >> keyword; low = 0; high = n-1; proses = 0; while(berhenti != true) { proses++; posisi = (((keyword-data[low])*(high-low))/(data[high]-data[low])+low); if(data[posisi] == keyword) { cout << "Data " << keyword << " pada posisi indeks ke-" << posisi <<endl; cout << "Proses pencarian sebanyak " << proses <<endl; berhenti = true; } else if(data[posisi] < keyword) { low = posisi + 1; } else { cout << "Data yang anda cari tidak ditemukan.\n"; berhenti = true; } } return 0;

}

OUTPUT PROGRAM