如何在 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中文网其他相关文章！