Carian binari ialah &mdash yang cekap; anggaran kerumitannya ialah O(log2(n)), manakala carian berjujukan konvensional mempunyai O(n). Ini bermakna, sebagai contoh, untuk tatasusunan 1024 elemen, carian linear, dalam kes paling teruk, apabila elemen yang dikehendaki tiada dalam tatasusunan, akan memproses semua 1024 elemen. Carian binari sudah cukup untuk memproses elemen \(log_2(1024) = 10\). Keputusan ini dicapai kerana fakta bahawa selepas langkah pertama gelung, kawasan carian mengecil kepada 512 elemen, selepas &ndash kedua; sehingga 256 dsb.
Kelemahan algoritma ini adalah keperluan untuk pesanan data, serta keupayaan untuk mengakses mana-mana elemen data dalam masa yang tetap (bebas daripada jumlah data). Oleh itu, algoritma tidak boleh berfungsi pada tatasusunan tidak tertib dan sebarang struktur data berdasarkan senarai terpaut.
Pelaksanaan
selamat tinggal (kanan – kiri > 1) // Asalkan sempadan kanan berada di sebelah kanan kiri
nc
tengah = (kiri + kanan) /< /span> 2; // Tengah kawasan carian
jika (A[middle] >= b) kemudian
kanan = tengah; // Gerakkan sempadan kanan
jika tidak
kiri = tengah; // Jika tidak, alihkan sempadan kiri
cc
jika (A[kanan] == X) kemudian
keluaran yang betul;
jika tidak
keluaran -1;
di mana:
A - tatasusunan sumber,
N - saiz tatasusunan,
X - nombor yang dikehendaki.
|