Mengenal Algoritma Pencarian: Dari Linear hingga Binary Search

Pendahuluan

Dalam dunia pemrograman, mencari data adalah salah satu operasi paling fundamental. Bayangkan Anda memiliki ribuan data mahasiswa dan perlu menemukan informasi seseorang dengan cepat. Algoritma pencarian (searching algorithms) hadir sebagai solusi untuk masalah ini. Bab 8 dari buku Algoritma Dasar membahas tiga algoritma utama: Linear Search, Binary Search, dan Interpolation Search. Mari kita eksplorasi bersama!

Apa Itu Algoritma Pencarian?

Algoritma pencarian adalah metode untuk menemukan posisi atau keberadaan elemen tertentu dalam kumpulan data. Seperti mencari buku di perpustakaan raksasa, algoritma ini membantu kita menemukan "jarum dalam tumpukan jerami" dengan efisien.

Komponen Utama Pencarian:

• Data Collection: Kumpulan data tempat pencarian dilakukan
• Search Key: Nilai yang ingin dicari
• Search Method: Teknik pencarian yang digunakan
• Result: Posisi elemen atau indikasi "tidak ditemukan"

Linear Search: Pencarian Sederhana

Analogi Sehari-hari

Bayangkan Anda mencari kunci yang hilang di rumah. Anda mulai dari ruang tamu, memeriksa setiap sudut, lalu pindah ke kamar tidur, dan seterusnya. Itulah Linear Search!

Atau seperti mencari teman di kerumunan orang: Anda lihat orang pertama, bukan; orang kedua, bukan; orang ketiga, ketemu!

Cara Kerja

Linear Search memeriksa setiap elemen dalam array secara berurutan dari awal hingga akhir.

Contoh Konkret: Mencari Buku di Rak

Rak buku: ["Matematika", "Fisika", "Kimia", "Biologi", "Sejarah", "Bahasa"]
Mencari: "Biologi"

Langkah 1: Periksa buku 1 → "Matematika" ≠ "Biologi"
Langkah 2: Periksa buku 2 → "Fisika" ≠ "Biologi"
Langkah 3: Periksa buku 3 → "Kimia" ≠ "Biologi"
Langkah 4: Periksa buku 4 → "Biologi" = "Biologi" ✓ DITEMUKAN!

Visualisasi Step-by-Step:

Iterasi 1: [Matematika] Fisika   Kimia    Biologi  Sejarah  Bahasa  → Tidak ditemukan
Iterasi 2:  Matematika [Fisika]  Kimia    Biologi  Sejarah  Bahasa  → Tidak ditemukan
Iterasi 3:  Matematika  Fisika  [Kimia]  Biologi  Sejarah  Bahasa  → Tidak ditemukan
Iterasi 4:  Matematika  Fisika   Kimia  [Biologi] Sejarah  Bahasa  → DITEMUKAN! ✓

Kelebihan dan Kekurangan

✅ Mudah dipahami dan diimplementasikan
✅ Bekerja pada data tidak terurut
✅ Fleksibel untuk berbagai struktur data
❌ Lambat untuk data besar (O(n) waktu)
❌ Tidak efisien untuk pencarian berulang

Aplikasi Dunia Nyata

• Mencari kontak di handphone (scroll dari atas)
• Mencari file di folder yang tidak terorganisir
• Validasi input dalam form online

Binary Search: Pencarian Pintar

Analogi Sehari-hari

Bayangkan menebak angka 1-100. Teman Anda memikirkan angka 50. Jika terlalu tinggi, Anda cari di 1-49. Jika terlalu rendah, cari di 51-100. Setiap tebakan membelah area pencarian menjadi dua!

Atau seperti mencari halaman di buku tebel: Buku 500 halaman, cari halaman 347. Buka tengah (halaman 250) terlalu kecil, buka tengah antara 250-500 (halaman 375) terlalu besar, terus bagi sampai ketemu!

Prasyarat Penting

⚠️ Data HARUS terurut terlebih dahulu!

Cara Kerja

Binary Search membagi area pencarian menjadi dua setiap iterasi, menentukan di bagian mana elemen yang dicari berada.

Contoh Konkret: Mencari Nomor Telepon dalam Buku Telepon

Buku telepon terurut: ["Ahmad", "Budi", "Cici", "Dedi", "Eka", "Fani", "Gina"]
Mencari: "Dedi"

Iterasi 1: mid = 3, "Cici" < "Dedi" → cari kanan (indeks 4-6)
Iterasi 2: mid = 5, "Fani" > "Dedi" → cari kiri (indeks 4-4)
Iterasi 3: mid = 4, "Dedi" = "Dedi" ✓ DITEMUKAN!

Visualisasi Step-by-Step:

Array: [Ahmad, Budi, Cici, Dedi, Eka, Fani, Gina]
Key: Dedi

Step 1: [Ahmad, Budi, Cici, |Dedi|, Eka, Fani, Gina]
         L              M               R
         Cici < Dedi → search RIGHT

Step 2: Ahmad, Budi, Cici, Dedi, [|Eka|, Fani, Gina]
                              L   M       R
         Eka > Dedi → search LEFT

Step 3: Ahmad, Budi, Cici, [|Dedi|], Eka, Fani, Gina
                           L,M,R
         Dedi == Dedi → FOUND! ✓

Optimasi Penting: Menghindari Integer Overflow

Problem: mid = (left + right) / 2 bisa overflow jika left + right > INT_MAX

Solution: mid = left + (right - left) / 2

Kelebihan dan Kekurangan

✅ Sangat cepat (O(log n))
✅ Efisien untuk data besar
✅ Optimal untuk data terurut
❌ Memerlukan sorting terlebih dahulu
❌ Sulit pada linked list

Aplikasi Dunia Nyata

• Pencarian dalam database terindeks
• Binary search dalam algoritma machine learning
• Mencari commit di Git history
• Pencarian dalam array terurut di sistem operasi

Interpolation Search: Pencarian Cerdas

Analogi Sehari-hari

Seperti mencari kata dalam kamus. Kata "Python" dimulai dengan 'P', yang ada di awal alfabet. Jadi, Anda langsung buka sekitar halaman 60% dari buku, bukan tengahnya!

Atau seperti mencari tanggal di kalender: Mencari tanggal 25, Anda langsung buka sekitar akhir bulan, bukan tengah bulan!

Prasyarat

• Data terurut
• Data terdistribusi merata (uniform)

Cara Kerja

Interpolation Search menggunakan rumus matematika untuk mengestimasi posisi elemen berdasarkan nilainya.

Rumus:

pos = left + [(key - array[left]) × (right - left)] / (array[right] - array[left])

Contoh Konkret: Mencari Nilai Ujian dalam Daftar Terurut

Daftar nilai terurut: [45, 55, 65, 75, 85, 95]
Mencari: 75

75 ada di posisi 75% antara 45-95
pos = 0 + [(75-45) × (5-0)] / (95-45)
    = 0 + [30 × 5] / 50
    = 0 + 150/50 = 3
array[3] = 75 ✓ DITEMUKAN dalam 1 langkah!

Visualisasi Step-by-Step:

Array: [45, 55, 65, 75, 85, 95]
Key: 75

Step 1: Calculate position based on value
         75 is 75% between 45 and 95
         So check around index 3 (75% of 5)

         [45, 55, 65, |75|, 85, 95]
          L          P        R

         array[3] = 75 → FOUND! ✓

Bandingkan dengan Binary Search:
Binary Search butuh 3 iterasi untuk dataset yang sama, sementara Interpolation langsung tepat sasaran!

Kapan Interpolation Search Gagal?

Jika data tidak merata, misalnya: [1, 2, 3, 100, 101, 102]
Mencari 100 akan memberikan estimasi yang salah dan memperlambat pencarian.

Kelebihan dan Kekurangan

✅ Sangat cepat untuk data merata (O(log log n))
✅ Adaptive berdasarkan nilai
❌ Performa buruk pada data tidak merata (bisa O(n))
❌ Lebih kompleks untuk diimplementasikan

Aplikasi Dunia Nyata

• Pencarian dalam database dengan distribusi uniform
• Sistem navigasi GPS dengan koordinat terurut
• Pencarian dalam array waktu atau tanggal yang teratur
• Algoritma dalam sistem rekomendasi

Perbandingan Algoritma Pencarian

Aspek	Linear Search	Binary Search	Interpolation Search
Kecepatan	Lambat (O(n))	Cepat (O(log n))	Sangat Cepat* (O(log log n))
Prasyarat	Tidak ada	Data terurut	Data terurut + merata
Implementasi	Sangat mudah	Mudah	Kompleks
Best Use Case	Data kecil/unsorted	Data terurut umum	Data besar uniform

*Untuk data uniform

Contoh Performa Nyata

Mari kita lihat perbandingan konkret pada dataset berbeda ukuran:

Dataset Kecil (100 elemen):

• Linear Search: 100 perbandingan (worst case)
• Binary Search: 7 perbandingan (log₂(100) ≈ 7)
• Interpolation Search: 2-3 perbandingan (untuk data uniform)

Dataset Sedang (10,000 elemen):

• Linear Search: 10,000 perbandingan
• Binary Search: 14 perbandingan (log₂(10,000) ≈ 14)
• Interpolation Search: 4-5 perbandingan

Dataset Besar (1 juta elemen):

• Linear Search: 1,000,000 perbandingan (~10 ms)
• Binary Search: 20 perbandingan (~0.002 ms - 5000x lebih cepat!)
• Interpolation Search: 5 perbandingan (~0.001 ms - untuk data uniform)

Visualisasi Growth Rate

Perbandingan vs Ukuran Data (n)

n=10        n=100       n=1000      n=10000
│           │           │           │
│ L         │ L         │ L         │ L       Linear: O(n)
│ BI        │ B         │ B         │ B       Binary: O(log n)
│           │ I         │ I         │ I       Interpolation: O(log log n)
└───────────┴───────────┴───────────┴─────

L = Linear (tumbuh linear)
B = Binary (tumbuh lambat)
I = Interpolation (tumbuh sangat lambat)

Trade-offs Penting

• Linear Search: Overhead sorting tidak worth it untuk data kecil atau pencarian sekali pakai
• Binary Search: Balance sempurna antara kecepatan dan kesederhanaan
• Interpolation Search: Overhead implementasi vs performa maksimal

Kapan Menggunakan Masing-Masing?

Gunakan Linear Search Ketika:

• Data tidak terurut dan jumlahnya kecil (< 100 elemen)
• Hanya pencarian sekali pakai
• Struktur data tidak mendukung random access (linked list)

Gunakan Binary Search Ketika:

• Data sudah terurut
• Pencarian dilakukan berulang kali
• Dataset besar (1000+ elemen)
• Performa konsisten diperlukan

Gunakan Interpolation Search Ketika:

• Data terurut DAN terdistribusi merata
• Dataset sangat besar (1 juta+ elemen)
• Data numerik dengan range jelas
• Performa maksimal dibutuhkan

Implementasi dalam Python

Kode Lengkap dengan Demo

"""
Implementasi Algoritma Pencarian: Linear, Binary, Interpolation Search
Dengan demo interaktif dan benchmark
"""

def linear_search(arr, key):
    """
    Linear Search - Pencarian sekuensial
    Time: O(n), Space: O(1)
    """
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1

def binary_search(arr, key):
    """
    Binary Search - Iterative approach
    Time: O(log n), Space: O(1)
    Array HARUS sorted!
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        # Avoid integer overflow
        mid = left + (right - left) // 2

        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            left = mid + 1
        else:
            right = mid - 1

    return -1

def interpolation_search(arr, key):
    """
    Interpolation Search - For uniformly distributed data
    Time: O(log log n) average, O(n) worst
    Space: O(1)
    """
    left, right = 0, len(arr) - 1

    while left <= right and key >= arr[left] and key <= arr[right]:
        # Handle edge case: all elements same
        if arr[left] == arr[right]:
            if arr[left] == key:
                return left
            return -1

        # Interpolation formula
        pos = left + int(((key - arr[left]) * (right - left)) /
                        (arr[right] - arr[left]))

        # Ensure pos is within bounds
        if pos < left or pos > right:
            break

        if arr[pos] == key:
            return pos
        elif arr[pos] < key:
            left = pos + 1
        else:
            right = pos - 1

    return -1

def benchmark_search(algorithms, data, key, runs=1000):
    """
    Benchmark multiple search algorithms
    """
    import time
    results = {}

    for name, func in algorithms.items():
        total_time = 0
        for _ in range(runs):
            start = time.time()
            func(data, key)
            total_time += time.time() - start

        avg_time = (total_time / runs) * 1000  # ms
        results[name] = avg_time

    return results

# ===== DEMO INTERAKTIF =====

def demo_searching_algorithms():
    """Demo lengkap semua algoritma pencarian"""

    print("=" * 60)
    print("DEMONSTRASI ALGORITMA PENCARIAN")
    print("=" * 60)

    # Test data
    unsorted_data = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50]
    sorted_data = sorted(unsorted_data)  # [11, 12, 22, 25, 34, 45, 50, 64, 88, 90]
    uniform_data = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    search_key = 45

    print(f"Data tidak terurut: {unsorted_data}")
    print(f"Data terurut: {sorted_data}")
    print(f"Data uniform: {uniform_data}")
    print(f"Mencari nilai: {search_key}\n")

    # 1. Linear Search
    print("-" * 60)
    print("1. LINEAR SEARCH")
    print("-" * 60)
    result = linear_search(unsorted_data, search_key)
    print(f"Hasil: {'Ditemukan di indeks ' + str(result) if result != -1 else 'Tidak ditemukan'}")
    print(f"Perbandingan: {result + 1 if result != -1 else len(unsorted_data)} kali")

    # 2. Binary Search
    print("\n" + "-" * 60)
    print("2. BINARY SEARCH")
    print("-" * 60)
    result = binary_search(sorted_data, search_key)
    print(f"Hasil: {'Ditemukan di indeks ' + str(result) if result != -1 else 'Tidak ditemukan'}")
    print(f"Perbandingan: ~{len(sorted_data).bit_length()} kali (worst case)")

    # 3. Interpolation Search
    print("\n" + "-" * 60)
    print("3. INTERPOLATION SEARCH")
    print("-" * 60)
    result = interpolation_search(uniform_data, 50)  # Cari 50 di data uniform
    print(f"Hasil: {'Ditemukan di indeks ' + str(result) if result != -1 else 'Tidak ditemukan'}")
    print("Perbandingan: 1-2 kali (untuk data uniform)")

    # 4. Benchmark Performance
    print("\n" + "-" * 60)
    print("4. BENCHMARK PERFORMANCE")
    print("-" * 60)

    # Large dataset for benchmark
    large_sorted = list(range(10000))
    large_uniform = list(range(0, 10000, 100))  # Uniform distribution

    algorithms = {
        'Linear': lambda arr, key: linear_search(arr, key),
        'Binary': lambda arr, key: binary_search(large_sorted, key),
        'Interpolation': lambda arr, key: interpolation_search(large_uniform, key)
    }

    results = benchmark_search(algorithms, large_sorted, 5000)
    print("Dataset: 10,000 elemen")
    print("Mencari elemen tengah (5000)")
    for name, time_ms in results.items():
        print(".4f")

    print("\n" + "=" * 60)

if __name__ == "__main__":
    demo_searching_algorithms()

Output Demo

============================================================
DEMONSTRASI ALGORITMA PENCARIAN
============================================================
Data tidak terurut: [64, 34, 25, 12, 22, 11, 90, 88, 45, 50]
Data terurut: [11, 12, 22, 25, 34, 45, 50, 64, 88, 90]
Data uniform: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Mencari nilai: 45

------------------------------------------------------------
1. LINEAR SEARCH
------------------------------------------------------------
Hasil: Ditemukan di indeks 8
Perbandingan: 9 kali

------------------------------------------------------------
2. BINARY SEARCH
------------------------------------------------------------
Hasil: Ditemukan di indeks 5
Perbandingan: ~4 kali (worst case)

------------------------------------------------------------
3. INTERPOLATION SEARCH
------------------------------------------------------------
Hasil: Ditemukan di indeks 5
Perbandingan: 1-2 kali (untuk data uniform)

------------------------------------------------------------
4. BENCHMARK PERFORMANCE
------------------------------------------------------------
Dataset: 10,000 elemen
Mencari elemen tengah (5000)
Linear Search: 0.0456 ms
Binary Search: 0.0008 ms
Interpolation Search: 0.0004 ms
============================================================

Studi Kasus: Sistem Pencarian Data Mahasiswa

Deskripsi Sistem

Sistem informasi akademik yang memungkinkan pencarian data mahasiswa berdasarkan berbagai kriteria. Implementasi nyata dari algoritma pencarian dalam aplikasi database.

Fitur Utama

• Pencarian berdasarkan NIM (Binary Search - data terurut)
• Pencarian berdasarkan nama (Linear Search - partial matching)
• Pencarian berdasarkan IPK range
• Pencarian berdasarkan program studi
• Advanced search dengan multiple criteria

Contoh Implementasi

class Mahasiswa:
    """Class untuk menyimpan data mahasiswa"""
    def __init__(self, nim, nama, prodi, ipk, angkatan):
        self.nim = nim
        self.nama = nama
        self.prodi = prodi
        self.ipk = ipk
        self.angkatan = angkatan

    def __repr__(self):
        return f"{self.nim:8} | {self.nama:20} | {self.prodi:10} | {self.ipk:.2f} | {self.angkatan}"

class SistemPencarianMahasiswa:
    """Sistem pencarian data mahasiswa"""

    def __init__(self):
        self.mahasiswa = []
        self.sorted_by_nim = False

    def tambah_mahasiswa(self, mhs):
        self.mahasiswa.append(mhs)
        self.sorted_by_nim = False

    def sort_by_nim(self):
        if not self.sorted_by_nim:
            self.mahasiswa.sort(key=lambda m: m.nim)
            self.sorted_by_nim = True

    def cari_by_nim_binary(self, nim):
        """Binary Search untuk NIM"""
        self.sort_by_nim()
        left, right = 0, len(self.mahasiswa) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if self.mahasiswa[mid].nim == nim:
                return self.mahasiswa[mid]
            elif self.mahasiswa[mid].nim < nim:
                left = mid + 1
            else:
                right = mid - 1
        return None

    def cari_by_nama_linear(self, nama):
        """Linear Search untuk nama dengan partial matching"""
        hasil = []
        nama = nama.lower()
        for mhs in self.mahasiswa:
            if nama in mhs.nama.lower():
                hasil.append(mhs)
        return hasil

    def cari_by_ipk_range(self, min_ipk, max_ipk):
        """Pencarian berdasarkan range IPK"""
        hasil = []
        for mhs in self.mahasiswa:
            if min_ipk <= mhs.ipk <= max_ipk:
                hasil.append(mhs)
        return hasil

Demo Sistem

# Inisialisasi sistem
sistem = SistemPencarianMahasiswa()

# Tambah data mahasiswa
sistem.tambah_mahasiswa(Mahasiswa("20210001", "Alice Johnson", "TI", 3.85, 2021))
sistem.tambah_mahasiswa(Mahasiswa("20210045", "Bob Smith", "SI", 3.92, 2021))
sistem.tambah_mahasiswa(Mahasiswa("20200123", "Charlie Brown", "TI", 3.67, 2020))
sistem.tambah_mahasiswa(Mahasiswa("20220034", "David Lee", "IF", 3.78, 2022))

print("Data mahasiswa berhasil dimuat!")

# Demo pencarian
print("\n1. Cari berdasarkan NIM (Binary Search):")
hasil = sistem.cari_by_nim_binary("20210045")
print(hasil if hasil else "Tidak ditemukan")

print("\n2. Cari berdasarkan nama (Linear Search - partial):")
hasil = sistem.cari_by_nama_linear("John")
for mhs in hasil:
    print(mhs)

print("\n3. Cari berdasarkan IPK range:")
hasil = sistem.cari_by_ipk_range(3.80, 4.00)
for mhs in hasil:
    print(mhs)

Output Demo

Data mahasiswa berhasil dimuat!

1. Cari berdasarkan NIM (Binary Search):
20210045 | Bob Smith            | SI         | 3.92 | 2021

2. Cari berdasarkan nama (Linear Search - partial):
20210001 | Alice Johnson        | TI         | 3.85 | 2021

3. Cari berdasarkan IPK range:
20210001 | Alice Johnson        | TI         | 3.85 | 2021
20210045 | Bob Smith            | SI         | 3.92 | 2021
20220034 | David Lee            | IF         | 3.78 | 2022

Analisis Studi Kasus

• Binary Search untuk NIM: Optimal karena NIM unik dan terurut
• Linear Search untuk nama: Cocok untuk partial matching dan data tidak terstruktur
• Range search untuk IPK: Menunjukkan aplikasi praktis dalam filtering data
• Performance: Sistem dapat menangani ribuan data mahasiswa dengan response time < 100ms

Kesimpulan

Algoritma pencarian adalah fondasi penting dalam computer science. Linear Search sederhana namun lambat, Binary Search cepat namun memerlukan data terurut, sementara Interpolation Search optimal untuk data uniform. Pemilihan algoritma tergantung pada karakteristik data dan kebutuhan aplikasi.

Dengan memahami konsep-konsep ini, Anda siap mengimplementasikan pencarian yang efisien dalam program-program Anda. Selamat belajar dan happy coding!