Searching adalah operasi fundamental untuk menemukan posisi sebuah nilai di dalam kumpulan data. Algoritma yang dipilih menentukan kecepatan respons aplikasi, terutama ketika data berukuran besar. Pada chapter ini kita akan membandingkan linear search dengan kompleksitas O(n) dan binary search dengan kompleksitas O(log n) pada array terurut. Pembaca juga akan memakai function binarySearch bawaan Kotlin stdlib dan memahami varian lower bound yang sering dipakai di soal kompetitif maupun implementasi database. Pemilihan algoritma yang tepat dapat mempercepat pencarian dari jutaan operasi menjadi belasan operasi.

Linear search memeriksa setiap elemen secara berurutan dari indeks pertama hingga target ditemukan atau array habis. Algoritma ini bekerja pada data terurut maupun tidak terurat. Kompleksitas waktu adalah O(n) pada kasus terburuk karena seluruh elemen dapat diperiksa.

kotlin Linear search 
fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return -1
}

Function mengembalikan indeks pertama tempat target ditemukan, atau -1 bila target tidak ada. Linear search cocok untuk data kecil atau data yang tidak terurut dan jarang dicari.

Binary search membutuhkan array yang sudah terurut. Algoritma membandingkan target dengan elemen tengah; bila lebih kecil, pencarian dilanjutkan di paruh kiri, bila lebih besar di paruh kanan. Setiap iterasi memotong ruang pencarian menjadi dua, sehingga kompleksitas waktu O(log n).

kotlin 
// Demo Searching Algorithms: linear search dan binary search.

// === Linear search: O(n) ===
fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return -1
}

// === Binary search iteratif: O(log n), array harus sorted ===
fun binarySearchIter(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.lastIndex
    while (low <= high) {
        val mid = (low + high) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1
}

// === Binary search rekursif ===
fun binarySearchRec(arr: IntArray, target: Int, low: Int = 0, high: Int = arr.lastIndex): Int {
    if (low > high) return -1
    val mid = (low + high) / 2
    return when {
        arr[mid] == target -> mid
        arr[mid] < target -> binarySearchRec(arr, target, mid + 1, high)
        else -> binarySearchRec(arr, target, low, mid - 1)
    }
}

// === Binary search via Kotlin stdlib ===
fun kotlinBinarySearch(arr: IntArray, target: Int): Int {
    return arr.binarySearch(target).let {
        if (it < 0) -1 else it
    }
}

// === Lower bound: index elemen pertama yang >= target ===
fun lowerBound(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.size
    while (low < high) {
        val mid = (low + high) / 2
        if (arr[mid] < target) low = mid + 1
        else high = mid
    }
    return low
}

// === Linear search dengan hitung operasi ===
fun linearSearchCounted(arr: IntArray, target: Int): Pair<Int, Int> {
    var steps = 0
    for (i in arr.indices) {
        steps++
        if (arr[i] == target) return i to steps
    }
    return -1 to steps
}

// === Binary search dengan hitung operasi ===
fun binarySearchCounted(arr: IntArray, target: Int): Pair<Int, Int> {
    var low = 0
    var high = arr.lastIndex
    var steps = 0
    while (low <= high) {
        steps++
        val mid = (low + high) / 2
        when {
            arr[mid] == target -> return mid to steps
            arr[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1 to steps
}

fun main() {
    println("=== Demo Searching Algorithms ===")

    val data = intArrayOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 99)
    println("Data (sorted): ${data.toList()}")

    println()
    println("--- Linear search O(n) ---")
    listOf(23, 91, 100, 2).forEach { target ->
        val idx = linearSearch(data, target)
        println("Cari $target: ${if (idx >= 0) "ditemukan di index $idx" else "tidak ada"}")
    }

    println()
    println("--- Binary search iteratif O(log n) ---")
    listOf(23, 91, 100, 2).forEach { target ->
        val idx = binarySearchIter(data, target)
        println("Cari $target: ${if (idx >= 0) "ditemukan di index $idx" else "tidak ada"}")
    }

    println()
    println("--- Binary search rekursif ---")
    listOf(23, 91, 100, 2).forEach { target ->
        val idx = binarySearchRec(data, target)
        println("Cari $target: ${if (idx >= 0) "ditemukan di index $idx" else "tidak ada"}")
    }

    println()
    println("--- Kotlin stdlib binarySearch ---")
    listOf(23, 91, 100, 2).forEach { target ->
        val idx = kotlinBinarySearch(data, target)
        println("Cari $target: ${if (idx >= 0) "ditemukan di index $idx" else "tidak ada"}")
    }

    println()
    println("--- Lower bound (elemen pertama >= target) ---")
    listOf(20, 23, 50, 100).forEach { target ->
        val idx = lowerBound(data, target)
        val valueStr = if (idx < data.size) data[idx].toString() else "out"
        println("Target $target -> lower bound index $idx (value: $valueStr)")
    }

    println()
    println("--- Perbandingan jumlah operasi pada array berukuran 1.000.000 ---")
    val besar = IntArray(1_000_000) { it * 2 }
    val target = 999_998
    val (_, linSteps) = linearSearchCounted(besar, target)
    val (_, binSteps) = binarySearchCounted(besar, target)
    println("Linear search: $linSteps langkah")
    println("Binary search: $binSteps langkah")
}

Output yang Dihasilkan:

text 
=== Demo Searching Algorithms ===
Data (sorted): [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 99]

--- Linear search O(n) ---
Cari 23: ditemukan di index 5
Cari 91: ditemukan di index 9
Cari 100: tidak ada
Cari 2: ditemukan di index 0

--- Binary search iteratif O(log n) ---
Cari 23: ditemukan di index 5
Cari 91: ditemukan di index 9
Cari 100: tidak ada
Cari 2: ditemukan di index 0

--- Binary search rekursif ---
Cari 23: ditemukan di index 5
Cari 91: ditemukan di index 9
Cari 100: tidak ada
Cari 2: ditemukan di index 0

--- Kotlin stdlib binarySearch ---
Cari 23: ditemukan di index 5
Cari 91: ditemukan di index 9
Cari 100: tidak ada
Cari 2: ditemukan di index 0

--- Lower bound (elemen pertama >= target) ---
Target 20 -> lower bound index 5 (value: 23)
Target 23 -> lower bound index 5 (value: 23)
Target 50 -> lower bound index 7 (value: 56)
Target 100 -> lower bound index 11 (value: out)

--- Perbandingan jumlah operasi pada array berukuran 1.000.000 ---
Linear search: 500000 langkah
Binary search: 1 langkah

Bedah Kode Baris-per-Baris #

Mari kita amati bagian-bagian kunci:

  1. linearSearch (baris 4-9): Loop for (i in arr.indices) memeriksa elemen satu per satu. Begitu arr[i] == target, function segera mengembalikan i. Bila loop selesai tanpa menemukan target, kembalikan -1.
  2. binarySearchIter (baris 12-24): Variabel low dan high menyimpan batas rentang pencarian. Setiap iterasi menghitung mid = (low + high) / 2, lalu membandingkan elemen tengah dengan target. Konstruksi when memutuskan apakah target ditemukan, di paruh kanan, atau di paruh kiri.
  3. binarySearchRec (baris 27-35): Versi rekursif memanggil dirinya sendiri dengan rentang yang dipersempit. Base case low > high menghentikan rekursi dan mengembalikan -1.
  4. kotlinBinarySearch (baris 38-42): Memanfaatkan arr.binarySearch(target) bawaan Kotlin. Function ini mengembalikan indeks jika ketemu, atau nilai negatif (−insertionPoint − 1) bila tidak ada. Blok let menormalisasi hasil menjadi -1 bila target tidak ditemukan.
  5. lowerBound (baris 45-54): Mencari indeks elemen pertama yang >= target. Inisialisasi high = arr.size (bukan lastIndex) agar hasil bisa menyatakan “semua elemen lebih kecil dari target”. Bila low berakhir sama dengan arr.size, berarti target lebih besar dari seluruh elemen.
  6. Perbandingan langkah (baris 127-132): Array berisi 1 juta elemen genap. Mencari 999.998 dengan linear search membutuhkan 500.000 langkah (indeks 499.999). Binary search hanya 1 langkah karena nilai ada tepat di tengah pada iterasi pertama—menunjukkan selisih dramatis antara O(n) dan O(log n).

Memilih Algoritma Pencarian #

Linear search unggal ketika data berukuran kecil, tidak terurut, atau hanya dicari sesekali. Binary search menjadi pilihan utama bila data besar, terurut, dan sering dicari. Untuk koleksi dinamis yang elemennya sering berubah, struktur TreeSet atau HashMap memberi keseimbangan antara insertion O(log n) dan lookup O(log n) atau O(1).

Penutup #

Pencarian adalah operasi yang muncul di banyak lapisan aplikasi—dari validasi input hingga query database. Linear search sederhana tetapi lambat untuk data besar, sedangkan binary search memanfaatkan sifat terurut untuk mencapai kompleksitas logaritmik. Pada chapter berikutnya kita akan membahas algoritma pengurutan yang menjadi prasyarat binary search.

Referensi #

Referensi Lanjutan #