到目前为止,我已经将数组存储在向量中,然后循环遍历向量以找到匹配元素,然后返回索引.
在C中有更快的方法吗？我用来存储数组的STL结构对我来说并不重要(它不一定是矢量).我的数组也是唯一的(没有重复元素)并且有序(例如,及时的日期列表).
解决方法
由于元素已排序,您可以使用二进制搜索来查找匹配元素. C标准库有一个std :: lower_bound算法,可用于此目的.为了清晰和简单,我建议将其包装在您自己的二进制搜索算法中：
/// Performs a binary search for an element
///
/// The range `[first,last)` must be ordered via `comparer`. If `value` is
/// found in the range,an iterator to the first element comparing equal to
/// `value` will be returned; if `value` is not found in the range,`last` is
/// returned.
template <typename RandomAccessIterator,typename Value,typename Comparer>
auto binary_search(RandomAccessIterator const first,RandomAccessIterator const last,Value const& value,Comparer comparer) -> RandomAccessIterator
{
RandomAccessIterator it(std::lower_bound(first,last,value,comparer));
if (it == last || comparer(*it,value) || comparer(value,*it))
return last;
return it;
}
(C标准库有一个std :: binary_search,但它返回一个bool：如果范围包含元素,则为true,否则为false.如果你想要元素的迭代器,它就无用了.)
一旦有了元素的迭代器,就可以使用std :: distance算法来计算范围内元素的索引.
