Bolehkah Anda Melaksanakan Algoritma Carian Binari yang Cekap dalam C yang Mengembalikan Iterator kepada Hasil Carian?

Mencari Algoritma Carian Binari yang Cekap dalam C

Pengaturcara sering berusaha untuk melaksanakan algoritma carian binari yang cekap yang memberikan faedah kerumitan masa logaritma . Satu keperluan biasa ialah untuk algoritma mengembalikan iterator yang menunjuk kepada hasil carian dan bukannya boolean ringkas yang menunjukkan kewujudannya.

Pustaka Standard C menyediakan std::binary_search dalam pengepala, tetapi ia hanya mengembalikan boolean. Seperti yang dinyatakan oleh penyoal, ini boleh mengecewakan untuk situasi di mana kelajuan carian binari diingini dan data diketahui diisih.

Nasib baik, terdapat pelaksanaan alternatif tersedia yang menawarkan fungsi yang diingini. Satu pilihan yang popular ialah menggunakan algoritma tersuai yang memanfaatkan fungsi std::lower_bound, std::upper_bound, atau std::equal_range. Berikut ialah versi ringkas pelaksanaan sedemikian:

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val < *i)) {
        return i;
    }

    // Otherwise, return the end iterator
    else {
        return end;
    }
}</code>

Sebagai alternatif, set std:: boleh digunakan, yang menjamin susunan elemen dan menyediakan kaedah cari yang mengembalikan lelaran kepada item yang diingini. Walau bagaimanapun, adalah penting untuk mempertimbangkan sama ada keperluan itu serasi dengan penggunaan set, terutamanya dalam kes di mana berbilang kejadian elemen yang sama perlu disimpan.

Atas ialah kandungan terperinci Bolehkah Anda Melaksanakan Algoritma Carian Binari yang Cekap dalam C yang Mengembalikan Iterator kepada Hasil Carian?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!