Algoritma Pencarian Beruntun - Tutorial Interaktif

🚶 Apa itu Pencarian Beruntun?

Definisi

Algoritma Pencarian Beruntun (Linear Search) adalah cara yang paling sederhana dan paling dasar untuk mencari sebuah item dalam daftar (atau array).

Analoginya

Bayangkan Anda sedang mencari kaus kaki hitam tertentu di dalam laci yang berisi banyak kaus kaki yang tidak diurutkan.

🎯 Cara Kerja Pencarian Beruntun

Algoritma ini bekerja dengan cara:

Mulai dari Awal: Dari item pertama dalam daftar
Cek Satu Per Satu: Bandingkan item yang dicari dengan item saat ini
Terus Maju: Jika tidak cocok, pindah ke item berikutnya
Berhenti: Ketika item ditemukan atau daftar habis

📊 Contoh: Mencari Nama "Budi"

Daftar: [Andi, Siti, Dewi, Budi, Rina, Eko]

Langkah	Item yang Dicek	Perbandingan	Hasil	Aksi
1	Andi	Andi == Budi?	Salah	Pindah ke berikutnya
2	Siti	Siti == Budi?	Salah	Pindah ke berikutnya
3	Dewi	Dewi == Budi?	Salah	Pindah ke berikutnya
4	Budi	Budi == Budi?	Benar!	Pencarian Selesai

💡 Intinya:

Pencarian beruntun adalah algoritma pencarian paling dasar yang memeriksa setiap elemen secara berurutan hingga item ditemukan atau daftar habis.

📏 Array Berurut vs Tidak Berurut

Perbedaan Utama

Pencarian beruntun bekerja pada array berurut dan tidak berurut, tetapi ada optimasi khusus untuk array berurut.

Fitur	Array Tidak Berurut	Array Berurut
Susunan Data	Elemen data acak, tidak ada pola	Elemen data tersusun (misalnya, dari terkecil ke terbesar)
Cara Kerja	Harus memeriksa semua elemen hingga item ditemukan atau daftar habis	Dapat berhenti lebih awal jika item yang dicari lebih kecil dari elemen yang sedang diperiksa
Waktu Terburuk	O(N)	O(N) (sama-sama harus memeriksa N elemen jika item ada di akhir)
Optimasi	Tidak ada optimasi yang bisa dilakukan	Bisa dioptimasi (early exit) untuk kasus item tidak ada di tengah

🎯 Penghentian Awal (Early Exit)

Pada array berurut, kita bisa berhenti lebih awal. Misalnya mencari angka 15 di [5, 10, 20, 25]:

Cek 5 (15 > 5) → Lanjut
Cek 10 (15 > 10) → Lanjut
Cek 20 (15 < 20) → STOP!

Karena 20 lebih besar dari 15, dan array sudah berurut, maka 15 pasti tidak ada di daftar ini.

💡 Intinya:

Array berurut memungkinkan penghentian awal yang menghemat waktu perbandingan pada kasus gagal pencarian.

🔍 Pencarian Biner (Binary Search)

Syarat Mutlak dan Konsep Dasar

Pencarian Biner hanya dapat bekerja pada Array atau Daftar yang SUDAH BERURUTAN (Sorted).

Konsep Inti

Daripada memeriksa setiap item satu per satu (seperti Pencarian Beruntun), Pencarian Biner bekerja dengan cara membelah dua (memecah) daftar secara berulang-ulang. Ini seperti mencari kata dalam kamus.

📚 Cara Kerja Pencarian Biner

Bayangkan Anda mencari angka 55 dalam daftar berurut yang panjang.

Langkah 1: Tentukan Titik Tengah (Midpoint)

Algoritma selalu memulai dengan menemukan elemen tengah dari daftar.

Analogi Kamus: Jika Anda mencari kata 'Zebra' di kamus yang tebal, Anda tidak akan mulai dari halaman A. Anda akan langsung membuka bagian tengah (misalnya, M atau N).

Langkah 2: Bandingkan Titik Tengah dengan Target

Ada tiga kemungkinan hasil perbandingan:

Cocok: Elemen tengah adalah sama dengan Target (55). Pencarian Selesai!
Target Lebih Kecil: Elemen tengah (60) lebih besar dari Target (55). Ini berarti, karena daftarnya berurut, Target pasti berada di paruh KIRI dari elemen tengah.
Target Lebih Besar: Elemen tengah (40) lebih kecil dari Target (55). Ini berarti Target pasti berada di paruh KANAN dari elemen tengah.

Langkah 3: Ulangi Pembelahan

Algoritma sekarang mengabaikan setengah daftar yang tidak mungkin mengandung Target.

Daftar yang tersisa (paruh kiri atau paruh kanan) menjadi "daftar baru" kita.

Ulangi Langkah 1 dan 2 pada daftar yang tersisa tersebut hingga Target ditemukan atau daftar habis.

⚡ Keunggulan: Kompleksitas Waktu (O Notasi)

Kecepatan Pencarian Biner adalah alasan utama penggunaannya.

Kompleksitas: $O(\log N)$ (Kompleksitas Logaritmik).

Artinya: Setiap kali ukuran daftar ($N$) menjadi dua kali lipat, waktu yang dibutuhkan hanya bertambah sedikit sekali.

Ukuran Daftar (N)	Max Perbandingan (Linear Search O(N))	Max Perbandingan (Binary Search O(logN))
10	10	4
1.000	1.000	10
1 Juta	1 Juta	20

Perhatikan betapa dramatisnya perbedaan waktu (jumlah langkah) yang dibutuhkan untuk data yang sangat besar!

📝 Penulisan Algoritma (Pseudocode)

FUNGSI BinarySearch (Array, Target)
  KIRI = 0
  KANAN = panjang Array - 1

  SELAMA KIRI KURANG DARI ATAU SAMA DENGAN KANAN LAKUKAN
    TENGAH = (KIRI + KANAN) dibagi 2 (ambil bilangan bulat)

    JIKA Array[TENGAH] SAMA DENGAN Target MAKA
      KEMBALIKAN TENGAH // Target Ditemukan

    SELAIN JIKA Array[TENGAH] KURANG DARI Target MAKA
      KIRI = TENGAH + 1 // Cari di paruh KANAN

    SELAIN
      KANAN = TENGAH - 1 // Cari di paruh KIRI

    AKHIR JIKA
  AKHIR SELAMA

  KEMBALIKAN -1 // Target Tidak Ditemukan
AKHIR FUNGSI
                    

💡 Kesimpulan:

Pencarian Biner adalah raja efisiensi untuk pencarian, asalkan Anda selalu bisa menjaga datanya dalam keadaan berurut. Jika data Anda sering berubah dan tidak sempat diurutkan, Pencarian Beruntun mungkin lebih praktis.

🎮 Game Interaktif

🔍 Visualisasi Pencarian Beruntun

Lihat bagaimana algoritma pencarian beruntun bekerja langkah demi langkah!

Target yang dicari:

Tipe Array:

Siap untuk memulai pencarian...

Langkah: 0

📝 Contoh Kode Pencarian Beruntun

Berikut adalah implementasi algoritma pencarian beruntun dalam berbagai bahasa pemrograman:

🐍 Python - Array Tidak Berurut

def linear_search_unsorted(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Item ditemukan
    return -1  # Item tidak ditemukan

# Contoh penggunaan
names = ["Andi", "Siti", "Dewi", "Budi", "Rina"]
result = linear_search_unsorted(names, "Budi")
print(f"Budi ditemukan di indeks: {result}")
                    

🐍 Python - Array Berurut (Early Exit)

def linear_search_sorted(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Item ditemukan
        elif arr[i] > target:
            return -1  # Early exit - item pasti tidak ada
    return -1  # Item tidak ditemukan

# Contoh penggunaan
numbers = [5, 10, 20, 25, 30]
result = linear_search_sorted(numbers, 15)
print(f"15 ditemukan di indeks: {result}")
                    

☕ Java - Array Tidak Berurut

public static int linearSearchUnsorted(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;  // Item ditemukan
        }
    }
    return -1;  // Item tidak ditemukan
}

// Contoh penggunaan
int[] numbers = {5, 2, 8, 1, 9};
int result = linearSearchUnsorted(numbers, 8);
System.out.println("8 ditemukan di indeks: " + result);
                    

📊 Analisis Kompleksitas

Pencarian beruntun memiliki kompleksitas waktu yang sederhana:

Kasus	Kompleksitas Waktu	Penjelasan
Terbaik	O(1)	Item ditemukan di posisi pertama
Rata-rata	O(N)	Item ditemukan di tengah array
Terburuk	O(N)	Item tidak ada atau di posisi terakhir

💡 Intinya:

Pencarian beruntun sangat cocok untuk array kecil atau array yang sering berubah. Untuk array besar yang sudah berurut, gunakan Binary Search (O(log N)).