使用迭代器位置的线性和二进制搜索

Question

我正在写两个函数，第一个函数执行线性搜索，如果它在矢量中，它应该返回第一个找到的值的位置。第二种方法是使用equal_range完成的二进制搜索，它应该返回与线性搜索相同的内容。目前他们正在检查每个值作为匹配。任何帮助表示赞赏。

int linearSearch(const vector<int>& vec, int z) 
{ 
    vector<int>::iterator iter = find(vec.begin(), vec.end(), z); 

    if (iter != vec.end()) 
     return (iter-vec.begin()); 

    else 
     return -1; 
} 

int binarySearch(const vector<int>& vec, int z) 
{ 
    pair<vector<int>::const_iterator, vector<int>::const_iterator> bounds; 

    bounds = equal_range(vec.begin(),vec.end(), z); 

    if (bounds.first != vec.end()) 
     return (bounds.first -vec.begin()); 

    else 
     return -1; 
} 

Answer 1

您的描述不清楚，但我会指出一些关于代码的问题。

在binarySearch()搜索，有

bounds = equal_range(vec.begin(),vec.end(), z); 

if (bounds.first != v.end()) 
    return (bounds.first -v.begin()); 

v不被任何声明。如果代码编译的话，大概它会在你没有显示的代码中声明。但它可能与vec没有任何关系。代码的行为（尤其是return）将不确定。

函数之间的一个相当根本的区别是因为std::equal_range()假定已排序（或分区）的范围，并且std::find()没有。