如何為排序的 C 容器實作基於迭代器的二分搜尋演算法？

C 容器的帶迭代器傳回的二分搜尋演算法

STL 的std::binary_search 演算法有效地辨識排序中元素的存在演算法容器，但它只傳回一個布林值。對於元素的確切位置至關重要的場景，您可能需要基於迭代器的搜尋演算法。

為了滿足此需求，可以採用以下自訂二分搜尋演算法：

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

演算法利用std::lower_bound 來找出容器中值的插入點（如果要插入的話） 。如果該值存在，則傳回迭代器；否則，返回結束迭代器。這種方法既保證了速度又保證了精度

你也可以考慮使用std::set，它提供了一個迭代器find(T key) 函數，可以直接傳回指向給定專案的迭代器。但是，這可能不適合需要重複元素的情況。

以上是如何為排序的 C 容器實作基於迭代器的二分搜尋演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！