Bagaimana untuk menggunakan Python untuk melaksanakan carian binari

Pertama, buat fungsi bernama binary_search: lulus dua parameter, senarai elemen dan nilai yang anda ingin cari.

def binary_search(_list, value):

Seterusnya, tentukan pembolehubah yang diperlukan di dalam fungsi Kunci kepada dikotomi ialah mencari dari tengah senarai ke kedua-dua belah (ungkapan mungkin tidak ketat, tetapi inilah maksudnya), jadi. demi gerak hati, tentukan kiri, kanan dan tengah ialah tiga pembolehubah, mewakili masing-masing: indeks permulaan, indeks penamat dan indeks tengah senarai.

    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

Langkah seterusnya ialah melaksanakan bahagian utama carian binari Mula-mula tentukan gelung sementara supaya carian dapat diteruskan dengan lancar Jika penyataan cawangan bersarang dalam fungsi sementara untuk melaksanakan pertimbangan bersyarat situasi:

1. _list[mid] == nilai: Nilai tengah merupakan nilai yang perlu kita cari, jadi pulangkan terus indeks yang sepadan.

2. Nilai _list[pertengahan] >

3._list[mid] < nilai: Nilai yang akan ditemui adalah di sebelah kanan pertengahan, kemas kini nilai kiri hingga pertengahan dan cari di sebelah kanan pertengahan.

Akhir sekali, kemas kini nilai pertengahan untuk memulakan pusingan carian seterusnya Pada masa yang sama, gunakan pernyataan sementara-lain untuk menilai situasi di mana ia tidak ditemui, dan berikan nilai pulangan.

    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1

Akhir sekali, kod lengkap dan prestasi ujian berjalan adalah seperti berikut:

""" a demo realize binary search"""
 
 
def binary_search(_list, value):
    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1
 
 
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

Keputusan berjalan:

Tiada nilai untuk ditemui :

Atas ialah kandungan terperinci Bagaimana untuk menggunakan Python untuk melaksanakan carian binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!