Algoritma Pencarian Biner Python

Cari daftar yang diurutkan dalam waktu logaritmik O(log n). Jalankan dan pahami pencarian biner dengan Python, termasuk logika langkah demi langkah, kasus edge, dan pengoptimalan.

Coba di Editor

Ikhtisar

Pencarian biner adalah algoritma yang sangat efisien untuk menemukan item dalam daftar yang diurutkan. Tidak seperti pencarian linier yang memindai setiap elemen secara berurutan dalam waktu O(n), pencarian biner bekerja dengan membagi interval pencarian menjadi dua berulang kali.

Pencarian dimulai dengan memeriksa elemen tengah array. Jika nilai target cocok dengan elemen tengah, posisinya dikembalikan. Jika targetnya lebih kecil, algoritme akan mempersempit pencariannya ke bagian bawah; jika targetnya lebih besar, maka akan dipersempit ke bagian atas. Proses ini berulang hingga elemen ditemukan atau ukuran subarray turun menjadi nol.

Untuk mengimplementasikan pencarian biner dengan Python, kami menggunakan dua pointer (rendah dan tinggi) untuk melacak batas pencarian aktif. Karena ruang pencarian berkurang setengahnya pada setiap langkah, algoritme dijalankan dalam waktu O(log n), sehingga ideal untuk database berukuran besar.

Kode & Output Eksekusi

Implementasi pencarian biner berulang standar yang mengembalikan indeks elemen target dalam daftar yang diurutkan.

binary_search.py

Coba di Editor

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Keluaran Terminal

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Implementasi Langkah demi Langkah

Pengindeksan kueri dan pencarian dalam tabel database
Menemukan nilai ambang batas atau batas dalam rentang matematika kontinu
Fungsi pelengkapan otomatis dan pencarian di bidang teks

Pertanyaan yang Sering Diajukan

Apakah daftarnya harus diurutkan agar pencarian biner dapat berfungsi?

Ya, pencarian biner sangat bergantung pada elemen yang diurutkan. Jika daftar tidak diurutkan, logika perbandingan akan rusak, dan Anda harus mengurutkan daftar terlebih dahulu atau menggunakan pencarian linier.

Mengapa menggunakan pencarian biner berulang daripada pencarian biner rekursif?

Meskipun pencarian biner rekursif itu elegan, pencarian biner berulang sering kali lebih disukai dalam produksi. Pendekatan berulang berjalan di O(1) ruang tambahan, sedangkan pencarian rekursif memerlukan ruang O(log n) karena tumpukan panggilan, sehingga berisiko meluapnya tumpukan pada masukan yang sangat besar.

Topik Terkait

Algoritma Penyortiran Python

Jelajahi algoritma pengurutan python. Visualisasikan pengurutan gelembung dan pengurutan gabungan secara asli dalam konteks IDE browser.

Tutorial Algoritma Pengurutan Penggabungan Python

Pelajari cara mengimplementasikan Pengurutan Gabung dengan Python. Contoh interaktif langkah demi langkah dari strategi pengurutan Divide and Conquer.

Panduan Algoritma Python Quicksort

Jelajahi algoritma quicksort dengan Python. Pelajari pemilihan pivot, partisi, dan rekursi dalam contoh pengkodean interaktif ini.