Bagaimanakah Saya Boleh Melaksanakan Carian Binari dalam Python dengan Cekap untuk Memeriksa Kewujudan Item?

Carian binari (carian halo) dalam Python

Python menyediakan fungsi perpustakaan untuk melaksanakan carian binari (juga dipanggil carian binari), Digunakan untuk mencari item dalam senarai diisih atau tupel. Walau bagaimanapun, fungsi ini masih mengembalikan kedudukan jika item tidak ditemui.

Untuk menyelesaikan masalah ini dan hanya mengesan jika item itu wujud, satu cara adalah dengan menggunakan fungsi bisect.bisect_left() untuk mencari kedudukan sisipan dan kemudian semak sama ada item pada kedudukan itu sama dengan item sasaran . Walau bagaimanapun, ini boleh membosankan dan juga memerlukan semakan sempadan apabila nombor itu lebih besar daripada nombor terbesar dalam senarai.

Disebabkan penggunaan ingatan, kamus dicadangkan sebagai alternatif dalam soalan. Walau bagaimanapun, ini mungkin memerlukan lebih kurang dua kali ganda keperluan memori.

Oleh itu, masalah ini boleh diselesaikan dengan melaksanakan carian binari menggunakan kod tersuai:

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                 # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

Fungsi ini menggunakan fungsi bisect_left() untuk mencari kedudukan sisipan, yang menunjukkan kedudukan item sasaran jika wujud , atau tunjukkan kedudukan yang berada di luar julat apabila ia tidak hadir. Anda boleh menentukan sama ada item sasaran wujud dengan menyemak sama ada item pada kedudukan itu sama dengan item sasaran.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Melaksanakan Carian Binari dalam Python dengan Cekap untuk Memeriksa Kewujudan Item?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!