Page 156 - MODUL ALGORTIMA DAN PEMROGRAMAN

Berdasarkan gambar 13.3 langkah terakhir, angka yang dicari dibandingkan dengan elemen
terakhir pada bagian pertama (yaitu 12). Mengingat nilai yang dicari dan nilai elemen terakhir

pada bagian pertama sama maka berarti pencarian telah selesai.

D. Interpolation Search

Interpolation search adalah pengembangan dari binary search, persamaan keduanya yaitu

sama sama digunakan untuk mencari suatu nilai pada data yang telah terurut, sedangkan
perbedaan keduanya terletak pada cara kerjanya. Binary search mencari data dengan membagi

array secara terus menerus, sedangkan pada binary search interpolation ini mencari data

dengan menggunakan Formula, yaitu sebagai berikut:

( − [ ]) ∗ (ℎ ℎ − )
pos = +
( [ℎ ℎ] − [ ])

Keterangan:

• Pos: variabel yang digunakan untuk menampung indeks atau posisi dimana program akan

mencari data
• Key: variabel yang berisi data atau nilai yang dicari

• Data: array yang menyimpan banyak nilai dengan tipe yang sama sekaligus

• Low: variabel yang menampung indeks paling awal pada array (indeks 0)
• High: variabel yang menampung indeks terakhir dari array (indeks n-1)

• Data[low]: nilai pada indeks low

• Data[high]: nilai pada indeks high

Untuk lebih jelasnya dapat kita lihat pada gambar berikut.

Gambar 13. 4 Ilustrasi Interpolation Search

E. Contoh Program
1. Contoh 1 – Program penggunaan sequential search

133