0

我正在为大学作业编写二进制搜索方法，虽然我觉得这是正确的做法，但我觉得运行时间比它应该的要长.. 有人看到这有什么错误吗？iterator是一个自定义类，没有什么花哨的，可以满足您的期望。vec是一个迭代器向量，它指向一个更大的链接列表，其中包含我“真正”搜索的内容

iterator searchVec(const I& item)
{
    int left = 0;
    int right = (int)vec.size()-1;
    int mid = (right+left)/2;

    while(*vec.at(left) != *vec.at(right)){
        mid = (right+left)/2;
        if (mid == 0 || mid == vec.size()-1){
            //nothign else to search, we didnt find anything
            return *vec.end();
        }
        if (*vec.at(mid) == item){
            return vec.at(mid);
        }
        else if (item > *vec.at(mid)){
            left = mid;
        }
        else if (item < *vec.at(mid)){
            right = mid;
        }
    }
    return vec.at(mid);
}
4

1 回答 1

0

一些想法：

  • 您正在std::vector::at使用与std::vector::operator[].
  • 您不能取消引用vec.end(). 通常，如果您想向调用者发出未找到任何项目的信号，则会返回它。但是在这里，由于您不返回 的迭代器vec，也许您应该使用布尔输出参数或异常来发出信号。
  • 循环条件对我来说看起来不正确。它似乎应该left <= right代替*vec[left] != *vec[right]. 然后循环的目的是选择项目。如果我们跳出循环，则找不到任何项目。

  • 如评论中所述，退出条件是无用的，并且会阻止查找第一个和最后一个元素。

        if (mid == 0 || mid == vec.size()-1)
        //nothign else to search, we didnt find anything
        return *vec.end();
    }

这是一个稍微更正的代码：

iterator searchVec(const I& item)
{
    int left = 0;
    int right = (int)vec.size()-1;
    int mid = (right+left)/2;

    while(left <= right) // corrected condition
    {
        mid = (right+left)/2;
        iterator it = vec[mid]; // avoid recomputing vec[mid]
        if (*it == item) // this can be moved in a else {} statement,
            return it;   // after the else if (no impact on performances I think)
        else if (item > *it)
            left = mid + 1; // you were not strictly decreasing the interval
        else if (item < *it)
            right = mid - 1; // same here
    }
    throw not_found();
}
于 2013-03-30T22:49:06.243 回答