如何为排序的 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中文网其他相关文章！