Bagaimana untuk Melaksanakan Algoritma Carian Binari Berasaskan Iterator untuk Bekas C Isih?

Algoritma Carian Perduaan dengan Pemulangan Iterator untuk Bekas C

Algoritma std::binary_search STL dengan cekap mengenal pasti kehadiran elemen dalam satu disusun bekas, tetapi ia hanya mengembalikan nilai boolean. Untuk senario di mana lokasi tepat elemen adalah penting, anda mungkin memerlukan algoritma carian berasaskan iterator.

Untuk menangani keperluan ini, algoritma carian binari tersuai berikut boleh digunakan:

<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 titik sisipan nilai dalam bekas (jika ia akan dimasukkan). Jika nilai ada, iterator dikembalikan; jika tidak, iterator akhir dikembalikan. Pendekatan ini memastikan kedua-dua kelajuan dan ketepatan

Anda juga boleh mempertimbangkan untuk menggunakan std::set, yang menyediakan fungsi find(T key) iterator yang secara langsung mengembalikan iterator yang menunjuk ke item yang diberikan. Walau bagaimanapun, ini mungkin tidak sesuai untuk kes di mana unsur pendua diperlukan.

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