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]

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!