Dalam dunia ilmu komputer, efisiensi adalah kunci utama dalam pengolahan data. Salah satu metode pencarian yang menonjol untuk data yang terurut adalah Interpolation Search. Berbeda dengan Binary Search yang selalu membagi data tepat di tengah, Interpolation Search melakukan estimasi posisi target berdasarkan nilai kunci yang dicari.
Metode ini bekerja mirip dengan cara manusia mencari kata dalam kamus atau mencari nama dalam buku telepon. Jika Anda mencari kata yang dimulai dengan huruf “B”, Anda tidak akan membuka halaman tengah kamus, melainkan cenderung membuka bagian awal. Logika inilah yang mendasari Interpolation Search.
Baca juga: Panduan Lengkap dan Contoh Soal SKB Analis Perdagangan
Prinsip Dasar dan Rumus Interpolation Search
Interpolation Search sangat efektif digunakan pada dataset yang terurut (sorted) dan memiliki distribusi nilai yang seragam (uniformly distributed). Algoritma ini menggunakan rumus posisi untuk memprediksi di mana data berada.
Rumus utama untuk menentukan posisi (pos) adalah sebagai berikut:
$$pos = low + \left[ \frac{key – data[low]}{data[high] – data[low]} \times (high – low) \right]$$
Keterangan variabel:
- pos: Indeks estimasi posisi yang akan diperiksa.
- low: Indeks terendah dalam rentang pencarian saat ini.
- high: Indeks tertinggi dalam rentang pencarian saat ini.
- key: Nilai yang sedang dicari.
- data[low]: Nilai elemen pada indeks terendah.
- data[high]: Nilai elemen pada indeks tertinggi.
Keunggulan dan Kelemahan
Setiap algoritma memiliki karakteristiknya sendiri. Berikut adalah beberapa poin penting mengenai performa Interpolation Search:
Keunggulan
Pada data yang terdistribusi secara merata, kompleksitas waktu rata-rata dari algoritma ini adalah $O(\log(\log n))$. Ini jauh lebih cepat dibandingkan Binary Search yang memiliki kompleksitas $O(\log n)$.
Kelemahan
Jika data tidak terdistribusi secara merata (misalnya terdapat lonjakan nilai yang ekstrem), performa algoritma ini dapat menurun drastis hingga mencapai $O(n)$, yang setara dengan Linear Search.
Langkah-langkah Algoritma Interpolation Search
- Tentukan nilai low sebagai 0 dan high sebagai n-1 (panjang array dikurangi satu).
- Selama nilai key berada di antara data[low] dan data[high], serta low tidak lebih besar dari high, lakukan perhitungan posisi menggunakan rumus.
- Jika data[pos] sama dengan key, maka pencarian berhasil dan indeks dikembalikan.
- Jika data[pos] lebih kecil dari key, maka ubah nilai low menjadi pos + 1.
- Jika data[pos] lebih besar dari key, maka ubah nilai high menjadi pos – 1.
- Ulangi proses hingga data ditemukan atau rentang pencarian habis.
Contoh Soal 1: Pencarian Data Terdistribusi Seragam
Misalkan kita memiliki sebuah array yang sudah terurut sebagai berikut:
A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Target yang ingin dicari (key) adalah 70.
Langkah 1: Inisialisasi
- low = 0 (data[low] = 10)
- high = 9 (data[high] = 100)
- key = 70
Langkah 2: Menghitung Posisi
Gunakan rumus:
pos = 0 + [(70 – 10) / (100 – 10) * (9 – 0)]
pos = 0 + [60 / 90 * 9]
pos = 0 + [0.666… * 9]
pos = 6
Langkah 3: Cek Nilai
Data pada indeks ke-6 (A[6]) adalah 70.
Karena A[6] == key, maka pencarian selesai. Data ditemukan pada indeks ke-6 hanya dalam satu kali perhitungan.
Contoh Soal 2: Pencarian dengan Beberapa Iterasi
Diketahui array B:
B = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]
Target yang ingin dicari (key) adalah 22.
Iterasi 1:
- low = 0, high = 14
- data[low] = 2, data[high] = 30
- pos = 0 + [(22 – 2) / (30 – 2) * (14 – 0)]
- pos = 0 + [20 / 28 * 14]
- pos = 0 + [0.714 * 14]
- pos = 10
Cek B[10]:
Nilai B[10] adalah 22.
Hasil: Data ditemukan pada indeks 10.
Contoh Soal 3: Kasus Data Tidak Ditemukan
Gunakan array yang sama dengan Contoh Soal 2, namun kita mencari key = 15.
Iterasi 1:
- low = 0, high = 14
- pos = 0 + [(15 – 2) / (30 – 2) * 14]
- pos = 0 + [13 / 28 * 14]
- pos = 6.5 (dibulatkan menjadi 6)
Cek B[6]:
B[6] bernilai 14. Karena 14 < 15, maka low naik menjadi pos + 1.
low = 7.
Iterasi 2:
- low = 7 (B[7] = 16), high = 14 (B[14] = 30)
- pos = 7 + [(15 – 16) / (30 – 16) * (14 – 7)]
- pos = 7 + [-1 / 14 * 7]
- pos = 7 – 0.5 = 6.5 (dibulatkan menjadi 6)
Pada titik ini, perhitungan posisi menghasilkan nilai di luar rentang low saat ini (low = 7). Algoritma akan mendeteksi bahwa key berada di luar jangkauan nilai yang mungkin atau low > high setelah penyesuaian berikutnya. Maka, pencarian dihentikan dan disimpulkan data tidak ada.
Perbandingan dengan Binary Search
Untuk memahami mengapa Interpolation Search sangat berguna, mari kita bandingkan melalui sebuah skenario.
Bayangkan Anda memiliki daftar angka dari 1 hingga 1.000.000 yang berurutan sempurna. Jika Anda mencari angka 999.999:
Binary Search akan membagi dua daftar berkali-kali (sekitar 20 kali) mulai dari 500.000, lalu 750.000, dan seterusnya.
Interpolation Search akan menghitung posisi dan langsung memprediksi bahwa 999.999 berada di bagian paling ujung kanan array. Dalam satu atau dua langkah, posisi tersebut ditemukan.
Namun, jika data memiliki distribusi seperti [1, 2, 3, 4, 1000], rumus interpolasi akan menjadi tidak akurat karena jarak antara 4 dan 1000 terlalu besar, sehingga prediksi posisi “meleset” jauh.
Implementasi dalam Kode Program (Pseudo-code)
Berikut adalah logika Interpolation Search dalam bentuk pseudo-code yang mudah dipahami:
Plaintext
fungsi interpolationSearch(arr, n, key):
low = 0
high = n - 1
selama low <= high dan key >= arr[low] dan key <= arr[high]:
jika low == high:
jika arr[low] == key return low
return -1
pos = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low]))
jika arr[pos] == key:
return pos
jika arr[pos] < key:
low = pos + 1
lainnya:
high = pos - 1
return -1
Baca juga: Rektor Universitas Teknokrat Indonesia Salurkan Donasi untuk Korban Bencana Sumatera melalui ICMI
Tips Menguasai Interpolation Search
Untuk menguasai materi ini, Anda perlu memperhatikan beberapa detail teknis saat mengerjakan soal:
- Pastikan Data Terurut: Jangan pernah menerapkan Interpolation Search pada data acak. Hasilnya tidak akan valid.
- Pembulatan: Saat menghitung posisi (pos), gunakan pembulatan ke bawah (floor) atau pembulatan standar karena indeks array harus berupa bilangan bulat.
- Kondisi Berhenti: Selalu pastikan kunci (key) berada dalam rentang minimum dan maksimum array sebelum menghitung posisi untuk menghindari pembagian dengan nol atau indeks di luar batas.
- Latihan Mandiri: Cobalah membuat deret angka dengan selisih yang tidak beraturan (misal selisih 2, lalu selisih 5) dan hitunglah secara manual menggunakan rumus di atas.
Interpolation Search adalah contoh sempurna bagaimana matematika dapat meningkatkan performa komputasi. Meskipun lebih kompleks secara rumus dibandingkan Linear Search, efisiensi yang ditawarkan untuk data skala besar sangatlah signifikan.
Dengan memahami contoh soal dan cara kerja rumusnya, Anda kini siap mengimplementasikan algoritma ini dalam berbagai kebutuhan pengolahan data atau menjawab soal-soal ujian algoritma dengan percaya diri.
Penulis: Aripin
Post Comment