Bagaimana untuk melaksanakan algoritma carian binari menggunakan Python?

PHPz
Lepaskan: 2023-09-20 13:24:24
asal
1484 orang telah melayarinya

Bagaimana untuk melaksanakan algoritma carian binari menggunakan Python?

Bagaimana untuk melaksanakan algoritma carian binari menggunakan Python?

Algoritma carian binari, juga dikenali sebagai algoritma carian binari, ialah algoritma carian yang cekap. Ia berfungsi pada tatasusunan atau senarai tersusun, mengecilkan carian dengan membandingkan nilai sasaran kepada elemen di tengah tatasusunan. Berikut akan memperkenalkan cara melaksanakan algoritma carian binari dalam Python dan memberikan contoh kod khusus.

  1. Idea algoritma:
  2. Bandingkan nilai sasaran dengan elemen di tengah tatasusunan
  3. Jika sama, kembalikan kedudukan elemen
  4. Jika nilai sasaran lebih besar daripada elemen di tengah, teruskan mencari dalam separuh kanan;
  5. Jika nilai sasaran lebih kecil daripada elemen di kedudukan tengah, teruskan carian di bahagian kiri
  6. Secara berterusan mengurangkan julat carian sebanyak separuh sehingga nilai sasaran ditemui atau julat carian kosong.
  7. Pelaksanaan kod:
    Berikut ialah contoh kod menggunakan Python untuk melaksanakan algoritma carian binari:
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
Salin selepas log masuk
  1. Contoh penggunaan:
    Seterusnya kami menggunakan tatasusunan tersusun untuk melaksanakan operasi carian sebenar. Katakan terdapat tatasusunan arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] disusun dalam tertib menaik, dan kita ingin mencari kedudukan nombor 10.
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 10

result = binary_search(arr, target)

if result != -1:
    print("目标值在数组中的位置是:", result)
else:
    print("数组中不存在目标值。")
Salin selepas log masuk

Selepas kod di atas dijalankan, hasil output ialah: "Kedudukan nilai sasaran dalam tatasusunan ialah: 9".

  1. Ringkasan:
    Melalui pengenalan artikel ini, kami telah mempelajari cara menggunakan Python untuk melaksanakan algoritma carian binari. Algoritma ini mempunyai kecekapan tinggi dalam mencari nilai sasaran dalam tatasusunan atau senarai tersusun, dan boleh meningkatkan kelajuan carian dengan banyak. Dalam aplikasi praktikal, kami boleh mengoptimumkan algoritma carian binari dengan sewajarnya mengikut keperluan untuk memenuhi keperluan lebih banyak senario. Pada masa yang sama, kami juga boleh menggunakan kaedah rekursif untuk melaksanakan algoritma carian binari, tetapi berhati-hati untuk mengelakkan masalah limpahan tindanan.

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

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!