如何在 C 中實作返回迭代器的二分查找演算法？

C 中的二分查找演算法回傳迭代器

在C 中，std::binary_search 演算法提供了一種便捷的方法對已排序的容器執行二分搜尋。然而，它只傳回一個布林值來指示元素是否存在，這對於某些應用程式來說可能不夠。

迭代器傳回演算法的要求

需要出現一個二分搜尋演算法，傳回指向結果的迭代器而不是布林值。這允許開發人員存取找到的實際元素或確定它是否不存在於容器中。

實現自訂二分搜尋演算法

因為沒有這樣的函數標準庫中提供了自訂實現，可以使用其他STL 函數來製作自訂實現，例如std::lower_bound、std::upper_bound 或std::equal_range .

範例實作

範例實作範例。

這是一個使用

<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

另一種選擇是使用std::set，它維護排序元素並提供方法find(T key)，該方法傳回指定項目的迭代器。但是，如果容器中需要同一元素的多個實例，則此方法可能不合適。

以上是如何在 C 中實作返回迭代器的二分查找演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！