Interpolation Search
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 :