您能用 C 實現高效的二分搜尋演算法，將迭代器返回搜尋結果嗎？

在C 中搜尋高效的二分搜尋演算法

程式設計師經常尋求實現高效的二分搜尋演算法，以提供對數時間複雜度的優勢。一個常見的要求是演算法傳回一個指向搜尋結果的迭代器，而不是一個指示其存在的簡單布林值。

C 標準函式庫在 中提供了 std::binary_search header，但它只傳回一個布林值。正如提問者所指出的，對於需要二分搜尋速度並且已知資料已排序的情況，這可能會令人沮喪。

幸運的是，有其他可用的實作可以提供所需的功能。一種流行的選擇是使用利用 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) {
    // 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>

或者，可以使用 std::set，它保證元素的順序並提供 find 方法，該方法將迭代器返回到所需的項目。但是，重要的是要考慮要求是否與集合的使用相容，特別是在需要儲存相同元素的多個實例的情況下。

以上是您能用 C 實現高效的二分搜尋演算法，將迭代器返回搜尋結果嗎？的詳細內容。更多資訊請關注PHP中文網其他相關文章！