Halo, teman-teman mahasiswa! Setelah kita kuasai Linear Search (yang rajin cek satu-satu) dan Binary Search (si pintar yang potong tengah), sekarang kita ketemu Interpolation Search – si jenius yang bisa lebih cepat lagi!
Bayangkan kamu nyari nomor telepon di buku telepon yang sudah terurut berdasarkan nama. Kamu nggak buka tengah-tengah doang (kayak binary), tapi langsung estimasi: "Nama 'Surya' pasti di deket akhir, soalnya abjad S deket Z!" Nah, interpolation search melakukan itu: mengestimasi posisi target berdasarkan perhitungan matematis sederhana, seperti interpolasi linier. Cocok banget buat data yang terurut dan merata (uniformly distributed).
Ilustrasi keren ini nunjukin cara interpolation search "menebak" posisi dengan rumus pintar, sering langsung loncat ke tempat yang tepat!
Apa Itu Interpolation Search? 🤓✨
Interpolation search adalah upgrade dari binary search. Daripada selalu ambil tengah, dia hitung posisi probabel target pakai rumus:
pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])
- Ini seperti prediksi linier: Asumsi nilai-nilai tersebar merata.
- Kalau data merata (misal angka 1,2,3,... atau 10,20,30,...), dia bisa ketemu dalam hampir 1-2 langkah aja! (Rata-rata O(log log n) – super cepat!)
- Kekurangan: Kalau data nggak merata (banyak kluster), bisa lebih lambat dari binary search.
Harus data sudah terurut ya!
Cara Kerja Langkah demi Langkah 📈
Contoh array: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Target: 80
- low=0, high=8 pos = 0 + ((80-10)*(8-0)) // (90-10) = (70*8)//80 = 560//80 = 7 arr[7]=80 → Langsung ketemu di langkah pertama! 🔥
Contoh lain target 30:
pos pertama = 0 + ((30-10)*8)//80 = 160//80 = 2 → arr[2]=30 → Ketemu cepet!
Gambar ini jelasin step by step dengan contoh visual, bikin langsung paham rumusnya kayak sulap!
Visual sederhana ini bandingin linear, binary, dan interpolation – lihat betapa interpolation-nya efisien!
Implementasi di Python 🐍
Mirip binary search, tapi ganti cara hitung mid jadi pos interpolasi.
def interpolation_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high and target >= arr[low] and target <= arr[high]:
if low == high: # Kalau hanya satu elemen
if arr[low] == target:
return low
return -1
# Rumus interpolasi
pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))
if arr[pos] == target:
return pos
elif arr[pos] < target:
low = pos + 1
else:
high = pos - 1
return -1 # Nggak ketemu
Hati-hati division by zero kalau arr[low] == arr[high], tapi loop while sudah handle.
Contoh 1: Data Merata, Ketemu Cepat! 👍
daftar_angka = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target = 80
hasil = interpolation_search(daftar_angka, target)
if hasil != -1:
print(f"Wow! {target} ketemu di index {hasil} – super cepat!")
else:
print("Nggak ada 😅")
Output: Wow! 80 ketemu di index 7 – super cepat!
Contoh 2: Cari Nilai di Awal/Tengah/Akhir
angka = [5, 10, 15, 20, 25, 30, 35, 40]
print(interpolation_search(angka, 5)) # 0 (awal)
print(interpolation_search(angka, 20)) # 3 (tengah-ish)
print(interpolation_search(angka, 40)) # 7 (akhir)
Sering ketemu dalam 1-2 langkah!
Contoh 3: Nggak Ketemu
print(interpolation_search(angka, 17)) # -1
Contoh 4: Data Lebih Besar (Uniform)
besar = list(range(0, 1001, 10)) # [0,10,20,...,1000]
target = 770
hasil = interpolation_search(besar, target)
print(f"{target} ada di index {hasil}") # Langsung tepat!
Bonus: Bandingkan dengan Binary Search 🆚
Interpolation sering lebih cepat kalau data merata.
Diagram ini nunjukin perbedaan jelas: Binary selalu tengah, Interpolation langsung "tebak" deket target. Mind-blowing!
Visual lain yang bandingin kecepatan – interpolation menang telak di data uniform!
Latihan Keren Buat Kamu! 💪🔥
- Tambahin counter langkah, bandingin berapa iterasi interpolation vs binary search.
- Coba di data nggak uniform (misal [1,2,3,100,101,102]) – lihat kadang lebih lambat!
- Buat versi rekursif (challenge!).
- Timing test besar:
arr = list(range(0, 1000001, 1))dan cari angka random.
Selamat praktikum, guys! Interpolation search ini seperti cheat code buat data merata – bikin kamu merasa pintar banget sebagai programmer 🤖💡 Paham kan sekarang? Coba langsung di Python, kalau bingung eksperimen aja. Keep exploring and have fun coding! 🎉🐍
Top comments (0)