如何在 C 中實現返回元素位置的二分查找演算法？

獲得一個「有用的」C 二分搜尋演算法

C STL 提供了一個binary_search 演算法，但它只傳回一個布林值，指示是否元素存在。對於需要元素的確切位置的情況，需要更全面的演算法。

一個選項是建立自訂二分搜尋函數。這是一個簡單的實作：

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Find the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

另一種方法是使用std::set，它會自動對元素進行排序並提供一個find(T key) 方法，該方法傳回項目的迭代器。但是，如果資料可能包含重複值，這可能不合適。

對於速度至關重要的情況，利用二分搜尋的優勢非常重要。當元素不存在時，lower_bound 和 upper_bound 演算法可能不夠用，因為它們可能不會傳回結束迭代器。上面提供的binary_find函數解決了這個問題並確保了正確的行為。

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