如何在 C 中使用二分查找來尋找元素索引？

C 中的高效二分查找實作

在排序容器中尋找元素的索引或迭代器是 C 中的基本操作。然而，標準函式庫的 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 有效地尋找指向所搜尋元素的迭代器。如果找到的值與 val 不匹配，則傳回 end() 迭代器。

替代解決方案

另一個選擇是使用std::set，它保證元素排序並提供find(T key) 方法，該方法返回給定專案的迭代器。但是，這可能不適合需要重複元素的情況。

以上是如何在 C 中使用二分查找來尋找元素索引？的詳細內容。更多資訊請關注PHP中文網其他相關文章！