Memahami Interpolation Search: Algoritma Pencarian untuk Data Terurut

Dalam dunia pemrograman, pencarian data adalah operasi yang sangat penting. Salah satu algoritma pencarian yang menarik dan efisien untuk data terurut adalah Interpolation Search. Algoritma ini merupakan pengembangan dari Binary Search, tetapi dengan pendekatan yang lebih cerdas dalam menebak posisi elemen yang dicari. Pada artikel ini, kita akan membahas pengenalan, cara kerja, contoh implementasi, hasil, dan kesimpulan mengenai Interpolation Search.

Introduction: Apa itu Interpolation Search?

Interpolation Search adalah algoritma pencarian yang dirancang untuk mencari elemen tertentu dalam array atau list yang sudah terurut. Algoritma ini bekerja dengan menebak posisi elemen yang dicari berdasarkan nilai elemen di ujung array. Dengan kata lain, Interpolation Search menggunakan interpolasi linear untuk memperkirakan lokasi elemen, sehingga lebih efisien daripada Binary Search dalam kasus tertentu.

Interpolation Search memiliki kompleksitas waktu rata-rata O(log log n) untuk data yang terdistribusi merata, tetapi bisa mencapai O(n) dalam kasus terburuk (misalnya, ketika data tidak terdistribusi merata). Algoritma ini cocok digunakan ketika data sudah terurut dan terdistribusi secara merata.

Cara Kerja Interpolation Search

Berikut adalah langkah-langkah cara kerja Interpolation Search:

1. Tentukan Rentang Pencarian:
   • Mulai dengan rentang pencarian dari indeks pertama (low) hingga indeks terakhir (high).
2. Hitung Posisi Perkiraan:
   • Gunakan rumus interpolasi untuk menebak posisi elemen yang dicari:
   •  

     pos=low+(((target−arr[low])×(high−low))/(arr[high]−arr[low]))​

   • Rumus ini memperkirakan posisi elemen berdasarkan nilai elemen di ujung array dan nilai elemen yang dicari.
3. Periksa Elemen di Posisi Perkiraan:
   • Jika elemen di posisi perkiraan sama dengan elemen yang dicari, kembalikan posisi tersebut.
   • Jika elemen di posisi perkiraan lebih kecil dari elemen yang dicari, geser rentang pencarian ke kanan (low = pos + 1).
   • Jika elemen di posisi perkiraan lebih besar dari elemen yang dicari, geser rentang pencarian ke kiri (high = pos - 1).
4. Ulangi Proses:
   • Ulangi langkah 2 dan 3 hingga elemen ditemukan atau rentang pencarian habis.
5. Kembalikan Hasil:
   • Jika elemen ditemukan, kembalikan indeksnya. Jika tidak, kembalikan nilai yang menunjukkan elemen tidak ditemukan (misalnya, -1).

Contoh Implementasi Interpolation Search dalam Kotlin

Berikut adalah contoh implementasi Interpolation Search menggunakan bahasa pemrograman Kotlin:

fun interpolationSearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.size - 1

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        // Hitung posisi perkiraan
        val pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])

        when {
            arr[pos] == target -> return pos // Elemen ditemukan
            arr[pos] < target -> low = pos + 1 // Geser ke kanan
            else -> high = pos - 1 // Geser ke kiri
        }
    }

    return -1 // Elemen tidak ditemukan
}

fun main() {
    val arr = intArrayOf(10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
    val target = 70
    val result = interpolationSearch(arr, target)

    if (result == -1) {
        println("Elemen tidak ditemukan")
    } else {
        println("Elemen ditemukan di indeks $result")
    }
}

Hasil dari Contoh Implementasi

Pada contoh di atas, kita memiliki array terurut:

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Dan kita ingin mencari elemen 70.

1. Rentang Awal: low = 0, high = 9.
2. Posisi Perkiraan:
   • Pertama: pos = 0 + ((70 - 10) * (9 - 0)) / (100 - 10) = 6.
   • Elemen di indeks 6 adalah 70, yang sama dengan elemen yang dicari.

Output:

Elemen ditemukan di indeks 6