Pencarian Biner di Python: Panduan Lengkap untuk Pencarian yang Efisien

Secara umum, algoritma adalah urutan instruksi yang tepat yang diikuti komputer untuk menyelesaikan tugas tertentu atau memecahkan masalah. Lihat posting blog kami, What is an Algorithm, untuk mempelajari berbagai jenis algoritma dalam machine learning.

Gambaran konsep

Pencarian biner adalah algoritma yang andal yang dirancang untuk secara efisien menemukan sebuah nilai dalam dataset yang telah diurutkan. Gagasan inti di balik pencarian biner sederhana: Alih-alih memeriksa setiap elemen dalam dataset satu per satu seperti pada pencarian linear, pencarian biner mempersempit rentang pencarian menjadi setengah di setiap langkah, sehingga prosesnya jauh lebih cepat.

Begini cara kerjanya:

1. Mulailah dengan membandingkan nilai target dengan elemen tengah dataset. Indeks untuk nilai tengah dihitung menggunakan rumus: middle = (low + high) / 2, di mana low adalah indeks elemen pertama dalam rentang pencarian saat ini, dan high adalah indeks elemen terakhir.
2. Bandingkan nilai tengah dengan target. Jika nilai target sama dengan elemen tengah, Anda telah menemukan indeksnya, dan pencarian selesai. Jika nilai target lebih kecil dari elemen tengah, pencarian dilanjutkan pada separuh kiri dataset. Jika nilai target lebih besar, pencarian dilanjutkan pada separuh kanan dataset.
3. Ulangi langkah 1–2. Rentang pencarian terus dibagi dua di setiap langkah. Ulangi proses hingga nilai target ditemukan atau rentang pencarian menjadi kosong.

Proses pencarian biner. Gambar oleh Penulis

Di atas adalah contoh sederhana yang menunjukkan konsep di balik pencarian biner.

Proses pembagian dua inilah yang membuat pencarian biner sangat efisien. Namun, penting untuk dicatat bahwa dataset harus diurutkan agar pencarian biner bekerja dengan benar. Jika data tidak diurutkan, algoritma tidak akan berfungsi sebagaimana mestinya. 

Lihat Data Structures: A Comprehensive Guide With Python Examples untuk mempelajari lebih lanjut tentang berbagai jenis struktur data yang mungkin ingin Anda telusuri.

Poin-poin penting yang perlu diingat

Poin-poin berikut menyoroti prinsip inti dari pencarian biner.

Efisiensi

Pencarian biner jauh lebih cepat daripada pencarian linear, terutama saat menangani dataset besar. Sementara pencarian linear memiliki kompleksitas waktu O(n), artinya dalam skenario terburuk harus memeriksa setiap elemen, pencarian biner lebih efisien. Kompleksitas waktunya O(log n), yang berarti ruang pencarian dibagi dua di setiap langkah, sehingga secara signifikan mengurangi jumlah perbandingan yang diperlukan.

Untuk penjelasan rinci tentang bagaimana algoritma dievaluasi, lihat Big O Notation and Time Complexity Guide: Intuition and Math. Opsi lainnya adalah tutorial Analyzing Complexity of Code through Python.

Persyaratan

Agar pencarian biner berfungsi, dataset harus diurutkan dalam urutan naik atau turun. Ini merupakan prasyarat karena algoritma bergantung pada urutan elemen untuk menentukan separuh dataset mana yang harus dicari selanjutnya. Jika data tidak diurutkan, pencarian biner tidak dapat secara akurat menemukan nilai target.

Fleksibilitas

Pencarian biner dapat diimplementasikan menggunakan pendekatan iteratif atau rekursif. Metode iteratif menggunakan loop untuk berulang kali membagi dua rentang pencarian. Metode rekursif membuat fungsi memanggil dirinya sendiri dengan rentang pencarian yang lebih kecil. Fleksibilitas ini cocok untuk berbagai penerapan.

Penerapan di Dunia Nyata

Pencarian biner adalah alat yang kuat. Efisiensinya dalam mempersempit rentang pencarian dengan cepat membuatnya sangat berharga, terutama saat menangani dataset besar di mana kinerja dan kecepatan sangat krusial. Mari jelajahi beberapa penerapan spesifik dan lihat bagaimana pencarian biner dibandingkan dengan algoritma lain.

Database

Dalam database, pencarian biner sering digunakan untuk dengan cepat menemukan rekaman dalam kolom yang telah diurutkan, seperti mencari pengguna tertentu dalam basis data yang diurutkan berdasarkan ID pengguna. Bayangkan basis data yang berisi jutaan rekaman. Pencarian linear mengharuskan memindai tiap rekaman satu per satu, yang bisa memakan waktu lama. Sebaliknya, pencarian biner dapat dengan cepat menemukan rekaman yang diinginkan dengan secara sistematis membagi dua ruang pencarian, sehingga secara signifikan mengurangi jumlah perbandingan yang dibutuhkan.

Data science

Menelusuri dataset besar yang telah diurutkan adalah tugas umum dalam data science. Misalnya, dalam analisis deret waktu, pencarian biner dapat digunakan untuk menemukan stempel waktu tertentu dalam urutan peristiwa yang telah diurutkan. Dalam machine learning, algoritma pencarian biner dapat digunakan untuk mengoptimalkan hyperparameter dengan menemukan nilai terbaik dalam suatu rentang.

Grafika komputer

Dalam grafika komputer, pencarian biner digunakan dalam algoritma yang membutuhkan presisi dan kecepatan. Salah satu contohnya adalah ray tracing, sebuah teknik rendering untuk mensimulasikan bagaimana cahaya berinteraksi dengan objek. Pencarian biner dapat digunakan untuk dengan cepat menemukan titik perpotongan antara sinar dan permukaan.

Penyusun bagi algoritma kompleks

Pencarian biner tidak hanya berguna secara mandiri; ia juga menjadi penyusun bagi algoritma dan struktur data yang lebih kompleks. Misalnya, pohon pencarian, seperti binary search tree (BST), dan pohon seimbang, seperti AVL tree, didasarkan pada prinsip pencarian biner. Struktur-struktur ini memungkinkan operasi pencarian, penyisipan, dan penghapusan yang efisien, sehingga berguna ketika data perlu diperbarui secara dinamis dan sering dicari. Pelajari lebih lanjut tentang pohon-pohon ini di AVL Tree: Complete Guide With Python Implementation.

Pencarian Biner vs. Algoritma Pencarian Lain

Mari kita lihat bagaimana pencarian biner dibandingkan dengan dua algoritma pencarian umum lainnya: pencarian linear dan hash lookup.

Pencarian linear

Pencarian linear adalah algoritma sederhana yang memeriksa setiap elemen dalam dataset secara berurutan. Algoritma ini jauh kurang efisien dibandingkan pencarian biner, dengan kompleksitas waktu O(n). Namun, pencarian linear tidak memerlukan data yang diurutkan, sehingga berguna dalam beberapa skenario.

Hash lookup

Hash lookup adalah algoritma efisien untuk dengan cepat menemukan nilai dalam dataset ketika nilai-nilai tersebut terkait dengan kunci unik. Algoritma ini bekerja dengan menerapkan fungsi hash pada kunci, yang menghitung indeks tempat nilai terkait disimpan dalam hash table. Ini memungkinkan pengambilan nilai secara hampir seketika, sering kali dalam waktu O(1). Namun, meskipun sangat cepat untuk menemukan elemen spesifik, hash lookup memerlukan memori tambahan untuk menyimpan hash table dan tidak cocok untuk pencarian dalam rentang nilai, suatu tugas yang lebih tepat ditangani oleh pencarian biner.

Mengimplementasikan Pencarian Biner di Python

Mari kita jelajahi beberapa cara untuk mengimplementasikan pencarian biner sederhana di Python. Namun terlebih dahulu, kita perlu menyiapkan dataset sederhana untuk digunakan dan nilai target yang akan dicari. Bayangkan kita memiliki array terurut berikut dan target pencarian:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 56Didukung oleh

Metode iteratif

Metode iteratif mungkin adalah pendekatan yang paling mudah. Dengan metode ini, kita menggunakan while loop untuk berulang kali membagi dua interval pencarian hingga menemukan target. Metode ini sering disukai karena kejelasan dan efisiensinya.

Berikut cara mengimplementasikan pencarian biner secara iteratif:

def binary_search_iterative(arr, target):
    # Define the search bounds
    left, right = 0, len(arr) - 1  
    while left <= right:
        # Calculate the middle index
        mid = left + (right - left) // 2  
        # If the middle element is the target, return its index
        if arr[mid] == target:
            return mid  
        # If the target is bigger, narrow the search to the right half
        elif arr[mid] < target: 
            left = mid + 1  
        # If the target is smaller, narrow the search to the left half
        else: 
            right = mid - 1  
    # Return -1 if the target is not found
    return -1 
    
# Run the iterative function
result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")Didukung oleh

Mari kita cermati kode ini:

• Kita mulai dengan menetapkan ‘left’ dan ‘right’ sebagai batas ruang pencarian. Awalnya, left adalah 0 (awal array), dan ‘right’ adalah len(arr) - 1 (akhir array).

• Di setiap iterasi, kita menghitung indeks tengah, yang merepresentasikan titik tengah interval pencarian saat ini. Ini dilakukan menggunakan rumus mid = left + (right - left) /2.

• Kemudian kita membandingkan elemen pada mid dengan target:

• Jika keduanya sama, kita telah menemukan target, dan fungsi mengembalikan mid.

• Jika elemen pada mid lebih kecil dari target, artinya target ada di separuh kanan, jadi kita ubah left menjadi mid + 1.

• Jika elemen pada mid lebih besar dari target, target ada di separuh kiri, jadi kita ubah right menjadi mid - 1.

• Loop berlanjut hingga target ditemukan atau hingga left melampaui right, yang berarti target tidak ada di dalam array.

Metode rekursif

Metode rekursif untuk pencarian biner adalah cara lain untuk mengimplementasikan algoritma ini. Alih-alih menggunakan loop, fungsi memanggil dirinya sendiri, menyesuaikan batas pencarian setiap kali hingga menemukan target atau memastikan bahwa target tidak ada.

Berikut cara mengimplementasikan pencarian biner secara rekursif:

def binary_search_recursive(arr, target, left, right):
    # If the search bounds cross, the target isn't in the array
    if left > right:  
        return -1
    # Calculate the middle index
    mid = left + (right - left) // 2 
    # If middle value equals the target, return the index
    if arr[mid] == target: 
        return mid  
    # If the target is bigger than the middle value, search in the right half
    elif arr[mid] < target: 
        return binary_search_recursive(arr, target, mid + 1, right)  
    # If the target is smaller than the middle value, search in the left half
    else: 
        return binary_search_recursive(arr, target, left, mid - 1)  

# Run the recursive function
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")Didukung oleh

Mari kita cermati kode ini:

• Fungsi rekursif dimulai dengan batas left dan right yang sama seperti pada fungsi iteratif.

• Pertama, fungsi memeriksa apakah left melampaui right. Jika ya, fungsi mengembalikan -1, yang menunjukkan bahwa target tidak ada di dalam array.

• Jika tidak, fungsi menghitung indeks mid dan membandingkan target dengan elemen pada mid.

• Jika target sama dengan elemen pada mid, fungsi mengembalikan mid.

• Jika target lebih besar dari mid, fungsi memanggil dirinya sendiri secara rekursif dengan batas yang diperbarui untuk mencari di separuh kanan.

• Jika target lebih kecil dari mid, fungsi mencari di separuh kiri.

• Rekursi berlanjut hingga target ditemukan atau ruang pencarian habis.

Untuk mempelajari lebih lanjut tentang fungsi rekursif, lihat Understanding Recursive Functions in Python.

Menggunakan modul bawaan bisect di Python

Pustaka standar Python menyertakan modul bisect, yang menyediakan fungsi pencarian biner siap pakai. Modul ini sangat efisien dan sering kali menghemat waktu dibandingkan membangun fungsi sendiri.

Berikut cara menggunakan modul bisect untuk menemukan target dalam array kita:

# Import the bisect module
import bisect 

# Call the module and provide the array and the target value
index = bisect.bisect_left(arr, target) 

#Print results
if index < len(arr) and arr[index] == target:
    print(f"Bisect: Target found at index {index}")
else:
    print("Bisect: Target not found")Didukung oleh

Mari kita cermati kode ini:

• Fungsi bisect_left mengembalikan indeks tempat target seharusnya disisipkan untuk mempertahankan urutan array. Jika target ditemukan pada indeks ini, berarti target ada di dalam array.

• Metode ini sangat berguna saat bekerja dengan array yang telah diurutkan dan juga dapat digunakan untuk menyisipkan elemen sambil mempertahankan urutan yang telah diurutkan.

• Modul bisect juga menyediakan fungsi lain seperti bisect_right dan insort, yang dapat digunakan untuk menemukan titik penyisipan atau menyisipkan elemen secara langsung.

Kompleksitas Waktu dan Ruang

Saat membahas efisiensi algoritma, kita sering menggunakan notasi Big O, direpresentasikan sebagai O(x), untuk menjelaskan bagaimana waktu eksekusi atau kebutuhan ruang bertambah seiring ukuran masukan meningkat. Untuk pencarian biner, kompleksitas waktunya biasanya O(log n). Ini berarti bahwa saat dataset tumbuh, jumlah operasi yang diperlukan untuk menemukan target meningkat secara logaritmik, membuat pencarian biner tetap efisien bahkan untuk dataset besar.

Metode iteratif pada pencarian biner memiliki kompleksitas waktu O(log n) karena interval pencarian dibagi dua di setiap iterasi. Kompleksitas ruangnya adalah O(1) karena hanya menggunakan ruang tambahan konstan, hanya membutuhkan beberapa variabel untuk melacak batas pencarian dan elemen tengah.

Metode rekursif juga memiliki kompleksitas waktu O(log n) dengan alasan yang sama. Namun, kompleksitas ruangnya adalah O(log n) karena ruang yang dibutuhkan untuk mempertahankan call stack untuk setiap pemanggilan rekursif. Karena setiap pemanggilan rekursif menambah satu lapisan pada stack, kedalaman rekursi sebanding dengan jumlah langkah pembagian dua, yang bersifat logaritmik terhadap ukuran dataset.

Meskipun keduanya efisien dari sisi waktu, pendekatan iteratif lebih hemat ruang. Inilah mengapa modul bisect menggunakan pendekatan iteratif di balik layar. Secara pribadi, saya juga lebih menyukai pendekatan iteratif karena alasan ini. Namun, pendekatan rekursif bisa lebih intuitif bagi sebagian orang dan mungkin memerlukan lebih sedikit baris kode.

Kesalahan Umum dan Cara Menghindarinya

Saat menggunakan pencarian biner, ada beberapa kesalahan umum yang perlu diwaspadai. Hal ini dapat memengaruhi kebenaran dan efisiensi algoritma Anda, sehingga penting untuk memperhatikannya.

Pertama, pencarian biner bergantung pada dataset yang telah diurutkan. Jika data tidak diurutkan, pencarian biner tidak akan berfungsi dengan benar; hasilnya bisa salah atau gagal sama sekali. Karena itu, penting untuk mengurutkan dataset sebelum menerapkan pencarian biner. Jika pengurutan data tidak memungkinkan, maka pencarian biner bukanlah alat yang tepat.

Masalah yang sering terjadi adalah kesalahan off-by-one. Kesalahan ini muncul ketika perhitungan indeks sedikit tidak tepat, yang berpotensi menyebabkan loop tak hingga atau gagal menemukan nilai target. Ini bisa terjadi jika perhitungan titik tengah atau penyesuaian batas tidak ditangani secara tepat. Untuk menghindarinya, pastikan perhitungan indeks tengah benar dan batas diperbarui dengan semestinya setelah setiap perbandingan. Ingat, nilai indeks di Python dimulai dari 0, bukan 1.

Tantangan lain yang perlu diperhatikan jika Anda menggunakan pencarian biner secara rekursif adalah masalah kedalaman rekursi. Di Python, ada batas jumlah pemanggilan rekursif untuk mencegah penggunaan memori berlebihan. Jika dataset Anda sangat besar, rekursi yang dalam dapat melampaui batas ini dan menyebabkan stack overflow. Untuk mengatasinya, pertimbangkan menggunakan pendekatan iteratif untuk pencarian biner, yang tidak memiliki batasan kedalaman rekursi. Jika rekursi lebih disukai atau diperlukan, Anda mungkin dapat meningkatkan batas rekursi menggunakan sys.setrecursionlimit(), tetapi ini harus dilakukan dengan hati-hati untuk menghindari potensi masalah lain.

Kesimpulan

Pencarian biner adalah algoritma yang kuat dan efisien yang seharusnya ada di perangkat setiap pengembang Python. Baik diimplementasikan secara iteratif maupun rekursif, algoritma ini menawarkan keunggulan kinerja yang signifikan dibandingkan pencarian linear, terutama pada dataset besar. Untuk materi lebih lanjut, lihat jalur keterampilan DataCamp’s Python Programming atau kursus interaktif Software Engineering Principles in Python.