Bagaimanakah Saya Boleh Semak Kehadiran Item dengan Cekap dalam Senarai Isih Menggunakan Carian Binari dalam Python?

Carian Perduaan (Bahagian) dalam Python dengan Semakan Kehadiran Item Eksplisit

Modul pembahagian dua Python menyediakan fungsi untuk melakukan carian binari, seperti bisekt_kiri dan belah_kanan. Walau bagaimanapun, fungsi ini mengembalikan kedudukan walaupun item yang dicari tidak terdapat dalam senarai. Untuk kes di mana hanya kehadiran atau ketiadaan item dikehendaki, semakan yang lebih jelas diperlukan.

Satu pendekatan ialah menggunakan dua belah kiri dan sahkan jika item pada kedudukan yang dikembalikan sepadan dengan sasaran. Walau bagaimanapun, kaedah ini memperkenalkan kerumitan tambahan, seperti semakan sempadan untuk kes yang sasarannya lebih besar daripada elemen terbesar dalam senarai.

Penyelesaian yang lebih mudah dan langsung ialah melaksanakan fungsi carian binari tersuai yang menyemak secara eksplisit untuk kehadiran item sebelum mengembalikan hasilnya. Berikut ialah contoh:

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 mengambil senarai diisih a, nilai sasaran x dan sempadan bawah dan atas pilihan untuk carian. Ia menggunakan bisect_left untuk mencari titik sisipan bagi x, kemudian menyemak sama ada item pada kedudukan itu sepadan dengan sasaran. Jika padanan ditemui, fungsi mengembalikan kedudukan; jika tidak, ia mengembalikan -1 untuk menunjukkan ketiadaan item.

Dengan memasukkan semakan eksplisit ini, anda boleh dengan cekap menentukan kehadiran atau ketiadaan item dalam senarai diisih tanpa memperkenalkan overhed atau pengehadan yang tidak perlu.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Semak Kehadiran Item dengan Cekap dalam Senarai Isih Menggunakan Carian Binari dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!