您能用 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中文网其他相关文章！