如何在 C 中实现返回迭代器的二分查找算法？

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

在 C 中，std::binary_search 算法提供了一种便捷的方法对已排序的容器执行二分搜索。然而，它只返回一个布尔值来指示元素是否存在，这对于某些应用程序来说可能不够。

迭代器返回算法的要求

需要出现一种二分搜索算法，返回指向结果的迭代器而不是布尔值。这允许开发人员访问找到的实际元素或确定它是否不存在于容器中。

实现自定义二分搜索算法

因为没有这样的函数标准库中提供了自定义实现，可以使用其他 STL 函数来制作自定义实现，例如 std::lower_bound、std::upper_bound 或 std::equal_range .

示例实现

这是一个使用 std::lower_bound:

<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::set

另一种选择是使用 std::set，它维护排序元素并提供方法 find(T key)，该方法返回指定项的迭代器。但是，如果容器中需要同一元素的多个实例，则此方法可能不合适。

以上是如何在 C 中实现返回迭代器的二分查找算法？的详细内容。更多信息请关注PHP中文网其他相关文章！