Bagaimana untuk Melaksanakan Algoritma Carian Binari dalam C Yang Mengembalikan Lokasi Elemen?

Mendapatkan Algoritma Carian Binari C "Berguna"

C STL menyediakan algoritma carian_binari, tetapi ia hanya mengembalikan boolean yang menunjukkan sama ada unsur wujud. Untuk kes di mana lokasi tepat elemen diperlukan, terdapat keperluan untuk algoritma yang lebih komprehensif.

Satu pilihan ialah mencipta fungsi carian binari tersuai. Berikut ialah pelaksanaan mudah:

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Find the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

Pendekatan lain ialah menggunakan std::set, yang secara automatik memesan elemen dan menyediakan kaedah find(T) yang mengembalikan iterator kepada item tersebut. Walau bagaimanapun, ini mungkin tidak sesuai jika data boleh mengandungi nilai pendua.

Untuk situasi di mana kelajuan adalah kritikal, adalah penting untuk memanfaatkan faedah carian binari. Algoritma lower_bound dan upper_bound boleh menjadi tidak mencukupi apabila elemen tidak wujud, kerana ia mungkin tidak mengembalikan lelaran akhir. Fungsi binary_find yang disediakan di atas menangani isu ini dan memastikan tingkah laku yang betul.

Atas ialah kandungan terperinci Bagaimana untuk Melaksanakan Algoritma Carian Binari dalam C Yang Mengembalikan Lokasi Elemen?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!