递归二进制搜索 'Out of Range'

Question

只是想知道是否有人可以帮助我尝试编写递归二进制搜索。目前正在抛出 'out of range' 错误：

terminate called after throwing an instance of 'std::out_of_range'
what():  vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)
Aborted (core dumped)

我确定这与我尝试编写正确的递归失败有关（我还是个新手）。如果有人可以提示我问题出在哪里，我将不胜感激。这是我的代码：

RecursiveBinarySearch.cpp

    // RecursiveBinarySearch class constructor.
RecursiveBinarySearch::RecursiveBinarySearch()
{

}

// Sets the object that is being searched for. 
// In this case, we are always looking for the integer '1'.
int obj = 1;

// Searching the vector given for obj. if obj is found the function returns true, otherwise it returns false.
bool RecursiveBinarySearch::binarySearch(std::vector<int> vec, int mid)
{
    int start = 0, end = vec.size() - 1;
    std::cout << "mid : " << mid << "\n";

    while (start + 1 < end)
    {

        if (vec.at(mid) == obj)
            return true;

        else if (vec.at(mid) > obj)
            //end = mid - 1;
            return binarySearch(vec, mid - 1);

        else
            //start = mid + 1;
            return binarySearch(vec, mid + 1);

    }

    if ((vec.at(start) == obj) || (vec.at(end) == obj))
        return true;
    else
    {
        return false;
    }
}

// RecursiveBinarySearch class destructor.
RecursiveBinarySearch::~RecursiveBinarySearch()
{

}

main.cpp:

int main()
{

    // The user inputs a string of numbers (e.g. "6 4 -2 88 ..etc") and those integers are then put into a vector named 'vec'.
    std::vector<int> vec;
    int vecSize = vec.size();
    int mid = (vec.at(0) + vec.at(vecSize - 1)) / 2;

    std::string line;
    if (getline(std::cin, line))
    {
        std::istringstream str(line);

        int value;
        str >> value;
        vec.push_back(value);
        while (str >> value)
        {
            vec.push_back(value);
        }
    }

    // Creating RecursiveBinarySearch object.
    RecursiveBinarySearch bSearch;
    RecursiveBinarySearch *ptrBSearch = &bSearch;
    bool bS = ptrBSearch->binarySearch(vec, mid);

    // Print out inputted integers.
    std::cout << "Binary Search Result: \n";
    std::cout << bS << "\n";

    return 0;
}

谢谢！

Answer 1

让我们仔细看看

    std::vector<int> vec;
    int vecSize = vec.size();
    int mid = (vec.at(0) + vec.at(vecSize - 1)) / 2;

将其分解，我们得到

    std::vector<int> vec;

创建一个空向量

    int vecSize = vec.size();

空向量的大小将为零，因此

    int mid = (vec.at(0) + vec.at(vecSize - 1)) / 2;

总是解析为

    int mid = (vec.at(0) + vec.at(0 - 1)) / 2;

并且vec.at(0 - 1)不是向量的好去处。

解决方案：在加载矢量后中后期计算。

作为事后的想法，考虑提供 binarySearch 要搜索的项目作为参数。当前实现不可重入。

Answer 2

仔细看看你的算法。需要注意的几点：

你的二进制搜索接受 2 个参数 vector 和 mid，binarySearch(std::vector vec, int mid) 对于任何递归算法，你需要有两件事，一个停止条件（这样你就不会陷入无限循环）和一个递归条件（每次递归都会让你更接近你的解决方案，如果是二分查找的话会减少一半的搜索 space ）在你的情况下，你传入的向量总是相同的，并且计算的开始和结束也都是相同的，导致每次搜索相同 space 。您需要递归地传入一个新的开始和结束，或者您需要在每次递归传递中修改您的向量。
你定义你mid如下： int mid = (vec.at(0) + vec.at(vecSize - 1)) / 2; 通过这样做，您将 mid 定义为向量的第一个和最后一个元素的平均值，而不是它们的位置。例如。 vector = [ 2, 5, 60, 75, 80]，你的 mid 将是 (2+80)/2 = 41，而 41 绝对不是你向量中的有效位置。你的中间值应该是 (0 + 4) / 2 即 = 2；您可以通过使用开始和结束来获得它，并且每次在递归函数中都应该重新计算。

Answer 3

超出范围只是意味着您的索引超出了给定序列容器的范围限制（低或高）。并支持您使用 at() 来解决问题。

您发布的代码有几个问题。其中，最具破坏性的是中点计算不当。您正在寻找价值平均值；不是中点，然后使用它们作为索引，这显然是错误的。您的初始 mid 值也是错误的，因为它是在容器中的任何元素之前获取的。

还有一点很重要，您应该使用对容器的 const 引用。否则，您会在每次递归调用时复制 整个容器 。这可能看起来没什么大不了的，但是用一亿个项目来做这件事，我向你保证，这将是非常昂贵的。

也就是说，您的设置 是错误的 。递归二进制搜索是关于分而治之的（我希望你知道）。作为对数搜索的要求，序列必须排序。除此之外，使用序列容器实现此目的的最直接方法需要您了解三件事：

你寻求的价值 (duh)
您开始的项目的索引（或迭代器）。
表示当前分区序列结束位置的过去索引（或结束迭代器）。

最后一个总是让人们对循环算法不熟悉，但是当你开始做数学时它是有意义的。简而言之，将其视为您不搜索的第一个索引，而不是搜索的包容性索引。它还使算法的编码（无论是迭代式还是递归式）变得简单明了。

只有当你具备以上所有条件时，你才能产生一个带有转义条件的递归算法，这很关键。您必须有办法停止做您正在做的事情。

使用您的参数列表并提供缺少的部分，递归版本如下所示：

bool binarySearchR(std::vector<int> const& v, size_t beg, size_t end, int val)
{
    // when these are equal it means there are no elements
    //  left to search, and that means no match was found.
    if (beg == end)
        return false;

    // find midpoint
    size_t mid = beg + (end-beg)/2;

    // if the test value is less, recurse to upper partition
    //  important: we just checked 'mid', so the lower point
    //  is one *past* that; therefore ++mid is the recursed
    //  'beg' index.
    if (v[mid] < val)
        return binarySearchR(v, ++mid, end, val);

    // if the test value is greater, recurse to lower partition
    //  important: we don't check the 'end' index, it's the
    //  stopping point so just pass it as the recursed 'end' index;
    //  'mid' is therefore not modified here.
    if (val < v[mid])
        return binarySearchR(v, beg, mid, val);

    // not lesser, not greater, thus equal
    return true;
}

您可以通过重载函数来进一步简化此操作，以简单地通过常量引用和值获取向量，然后调用递归函数：

bool binarySearchR(std::vector<int> const& v, int val)
{
    return binarySearchR(v, 0, v.size(), val);
}

这允许您像这样调用它：

int main()
{
    std::vector<int> vec { 1,2,3,4,6,9,10 };
    std::cout << std::boolalpha;

    for (int i=-1; i<=11; ++i)
        std::cout << std::setw(2) << i << ':' << binarySearchR(vec, i) << '\n';
}

输出

-1:false
 0:false
 1:true
 2:true
 3:true
 4:true
 5:false
 6:true
 7:false
 8:false
 9:true
10:true
11:false

输出符合预期，测试值和边缘情况正常工作。

基于迭代器的递归二进制搜索

基于迭代器的方法更符合现代 C++ 的工作方式，并且作为奖励将操作扩展到其他序列容器，例如 std::deque。它遵循与上述相同的总体设计，但使用基于模板的 Iter 类型：

template<class Iter>
bool binarySearchR(Iter beg, Iter end, typename std::iterator_traits<Iter>::value_type const& arg)
{
    if (beg == end)
        return false;

    Iter mid = std::next(beg, std::distance(beg,end)/2);
    if (*mid < arg)
        return binarySearchR(++mid, end, arg);

    if (arg < *mid)
        return binarySearchR(beg, mid, arg);

    return true;
}

我们同样可以重载它以只获取一个向量（我们假设它是排序的）和一个测试值，但为什么要到此为止。我们可以制作一个模板，将模板类型作为参数之一，感谢 C++11 和可变模板参数，它带来了一个优雅的解决方案：

template<class T, template<class, class...> class C, class... Args>
bool binarySearchR(C<T,Args...> const& seq, T const& val)
{
    return binarySearchR(std::begin(seq), std::end(seq), val);
}

上一节中的相同测试程序将运行，并产生相同的结果。

无递归的二分搜索

一旦掌握了该算法的窍门，您很快就会发现它非常适合迭代算法而不是递归算法。老实说，就调用堆栈而言，这并不重要 space。对 24 亿个已排序项目的二分查找最多只会递归 31 次，但这仍然是不必要的调用，如果我们能避免它们就好了。此外它可能会优化得更好，这总是值得考虑的事情：

template<class Iter>
bool binarySearchI(Iter beg, Iter end, typename std::iterator_traits<Iter>::value_type const& arg)
{
    while (beg != end)
    {
        Iter mid = std::next(beg, std::distance(beg,end)/2);
        if (*mid < arg)
            beg = ++mid;
        else if (arg < *mid)
            end = mid;
        else return true;
    }
    return false;
}

同样的重载适用：

template<class T, template<class, class...> class C, class... Args>
bool binarySearchI(C<T,Args...> const& seq, T const& val)
{
    return binarySearchI(std::begin(seq), std::end(seq), val);
}

它产生的结果与我们预期的相同。

递归二进制搜索 'Out of Range'

Recursive Binary Search 'Out of Range'

c++

recursion

binary-search

indexoutofrangeexception