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 && !(val <p>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().</p>
<p><strong>Penyelesaian Alternatif</strong></p>
<p>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.</p></class></code>

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!