Bagaimana untuk Melaksanakan Algoritma Carian Binari yang Mengembalikan Iterator dalam C?

Binary Search Algorithm Returning Iterator in C

Dalam C , algoritma std::binary_search menyediakan cara yang mudah untuk melakukan carian binari pada bekas yang diisih. Walau bagaimanapun, ia hanya mengembalikan boolean yang menunjukkan sama ada unsur itu wujud, yang mungkin tidak mencukupi untuk sesetengah aplikasi.

Keperluan untuk Algoritma Pemulangan Iterator

Keperluan timbul untuk algoritma carian binari yang mengembalikan iterator yang menunjuk kepada hasil dan bukannya boolean. Ini membolehkan pembangun mengakses elemen sebenar yang ditemui atau menentukan sama ada ia tidak terdapat dalam bekas.

Melaksanakan Algoritma Carian Binari Tersuai

Memandangkan tiada fungsi sedemikian tersedia dalam pustaka standard, pelaksanaan tersuai boleh dibuat menggunakan fungsi STL lain seperti std::lower_bound, std::upper_bound atau std::equal_range .

Sampel Pelaksanaan

Berikut ialah pelaksanaan mudah yang menggunakan std::lower_bound:

<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>

Sebagai alternatif, Menggunakan std::set

Pilihan lain ialah menggunakan std::set, yang mengekalkan elemen diisih dan menyediakan kaedah find(T key) yang mengembalikan iterator kepada item yang ditentukan . Walau bagaimanapun, pendekatan ini mungkin tidak sesuai jika berbilang tika elemen yang sama diperlukan dalam bekas.

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