Bagaimana Mencari Indeks Unsur dengan Carian Binari dalam C?

Implementasi Carian Binari yang Cekap dalam C

Mencari indeks atau lelaran elemen dalam bekas yang diisih ialah operasi asas dalam C . Walau bagaimanapun, algoritma std::binary_search perpustakaan standard hanya mengembalikan boolean yang menunjukkan kewujudan elemen, bukan kedudukannya.

Pertimbangkan kes di mana bekas diisih dan algoritma carian binari adalah lebih baik atas sebab kecekapan . Pelaksanaan yang memenuhi keperluan ini diperlukan.

Carian Perduaan Iteratif Tersuai

Satu pendekatan ialah melaksanakan algoritma carian binari berulang tersuai. Berikut ialah contoh pelaksanaan:

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

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

Algoritma ini menggunakan std::lower_bound untuk mencari iterator yang menunjuk ke elemen yang dicari dengan cekap. Jika nilai yang ditemui tidak sepadan dengan val, ia mengembalikan lelaran end().

Penyelesaian Alternatif

Pilihan lain ialah menggunakan set std::set, yang menjamin penyusunan elemen dan menyediakan kaedah find(T) yang mengembalikan iterator kepada item yang diberikan. Walau bagaimanapun, ini mungkin tidak sesuai untuk kes di mana unsur pendua diperlukan.

Atas ialah kandungan terperinci Bagaimana Mencari Indeks Unsur dengan Carian Binari dalam C?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!