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