Pencarian Linear dan Biner (Binary Search) di Python

Pencarian linear (linear search) memeriksa data satu per satu dari awal sampai target ditemukan. Pencarian biner (binary search) bekerja pada data yang sudah terurut dengan memeriksa elemen tengah, lalu membuang separuh data setiap langkah. Untuk 1.000 data, pencarian linear bisa membutuhkan 1.000 pemeriksaan, sedangkan pencarian biner paling banyak 10.

Apa Itu Algoritma Pencarian?

Algoritma pencarian (searching) adalah langkah-langkah untuk menemukan posisi suatu nilai, yang disebut target, di dalam sekumpulan data. Contohnya mencari nama di daftar hadir, kata di kamus, atau nomor di buku telepon. Hasilnya biasanya berupa indeks target, atau tanda khusus seperti -1 jika target tidak ditemukan.

Cara Kerja Pencarian Linear

1. Mulai dari elemen pertama.
2. Bandingkan elemen itu dengan target.
3. Jika sama, kembalikan indeksnya dan berhenti.
4. Jika tidak, pindah ke elemen berikutnya.
5. Jika semua elemen sudah diperiksa, target tidak ada; kembalikan -1.

Contoh 1: Pencarian linear di Python

def pencarian_linear(data, target):
    for indeks, item in enumerate(data):
        if item == target:
            return indeks
    return -1

nama = ["Ayu", "Bima", "Cici", "Dodi"]
print(pencarian_linear(nama, "Cici"))
print(pencarian_linear(nama, "Eka"))

Untuk "Cici", fungsi memeriksa Ayu, Bima, lalu Cici, dan mengembalikan 2. Untuk "Eka", keempat pemeriksaan gagal sehingga hasilnya -1. Fungsi enumerate memberi indeks dan nilai sekaligus di setiap putaran.

Cara Kerja Pencarian Biner (Binary Search)

Pencarian biner mirip cara kamu mencari kata di kamus: buka bagian tengah, lalu putuskan apakah harus ke kiri atau ke kanan.

1. Tandai batas kiri (indeks pertama) dan kanan (indeks terakhir).
2. Ambil indeks tengah: tengah = (kiri + kanan) // 2.
3. Jika elemen tengah sama dengan target, selesai.
4. Jika elemen tengah lebih kecil dari target, target pasti di kanan: kiri = tengah + 1.
5. Jika elemen tengah lebih besar, target pasti di kiri: kanan = tengah - 1.
6. Ulangi selama kiri <= kanan. Jika batas sudah bersilangan, target tidak ada.

Contoh 2: Menelusuri pencarian biner

Data terurut [3, 8, 12, 17, 21, 25, 30, 36, 41] (indeks 0–8), target 30.

Langkah	kiri	kanan	tengah	data[tengah]	Keputusan
1	0	8	4	21	21 < 30, geser ke kanan
2	5	8	6	30	ditemukan di indeks 6

Hanya 2 pemeriksaan, sedangkan pencarian linear membutuhkan 7.

Contoh 3: Kode binary search Python

def pencarian_biner(data, target):
    kiri, kanan = 0, len(data) - 1
    while kiri <= kanan:
        tengah = (kiri + kanan) // 2
        if data[tengah] == target:
            return tengah
        elif data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    return -1

angka = [3, 8, 12, 17, 21, 25, 30, 36, 41]
print(pencarian_biner(angka, 30))
print(pencarian_biner(angka, 5))

Keluarannya 6 dan -1. Untuk target 5, elemen yang diperiksa adalah 21, 8, lalu 3. Setelah itu kiri menjadi 1 dan kanan menjadi 0, sehingga perulangan berhenti.

Berapa Langkah yang Dibutuhkan?

Banyak data	Linear (terburuk)	Biner (terburuk)
10	10	4
100	100	7
1.000	1.000	10
1.000.000	1.000.000	20

Setiap kali data berlipat dua, pencarian biner hanya butuh satu pemeriksaan tambahan. Dalam notasi Big O, pencarian linear berkompleksitas $O(n)$ dan pencarian biner $O(\log n)$. Penjelasan lengkapnya ada di materi notasi Big O dan kompleksitas waktu.

Pencarian di Python Sehari-hari

Untuk program biasa, kamu tidak perlu selalu menulis fungsi sendiri. Operator in dan method index() pada list bekerja secara linear. Untuk list terurut, modul bawaan bisect menyediakan pencarian biner.

import bisect

nama = ["Ayu", "Bima", "Cici", "Dodi"]
print("Cici" in nama, nama.index("Cici"))

angka = [3, 8, 12, 17, 21, 25, 30, 36, 41]
print(bisect.bisect_left(angka, 30))

Keluarannya True 2 dan 6.

Kesalahan yang Sering Terjadi

Ringkasan

• Pencarian linear memeriksa satu per satu dan bisa dipakai pada data acak.
• Pencarian biner membagi dua ruang pencarian dan hanya untuk data terurut.
• Untuk $n$ data, linear paling banyak $n$ langkah; biner sekitar $\log_2 n$ langkah.
• Python menyediakan in, index(), dan modul bisect.

Materi Terkait

Pencarian bekerja pada list Python dan ditulis sebagai fungsi Python. Untuk membandingkan efisiensi algoritma secara umum, lanjutkan ke notasi Big O dan kompleksitas waktu.

def langkah_linear(data, target):
    langkah = 0
    for item in data:
        langkah += 1
        if item == target:
            break
    return langkah


def langkah_biner(data, target):
    kiri, kanan, langkah = 0, len(data) - 1, 0
    while kiri <= kanan:
        tengah = (kiri + kanan) // 2
        langkah += 1
        if data[tengah] == target:
            break
        elif data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    return langkah


data = list(range(1, 1001))
print("Linear:", langkah_linear(data, 1000))
print("Biner:", langkah_biner(data, 1000))

Sumber belajar

• BBC Bitesize KS3 Computer Science: Searching algorithms
• MIT OpenCourseWare 6.0001: Lecture 12, Searching and Sorting
• Python Standard Library: bisect
• Python Tutorial: Data Structures

Penjelasan dan contoh disusun ulang untuk materi ini; sumber dapat dibuka untuk belajar lebih lanjut.