c++ - 递归二进制搜索 'Out of Range'

Question

只是想知道是否有人可以帮助我尝试编写递归二进制搜索。 目前正在抛出“超出范围”错误:

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)

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

递归二进制搜索.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()
{

}

主要.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

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

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

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

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

• 你寻求的值(value)(废话)
• 您开始使用的项目的索引(或迭代器)。
• 表示当前分区序列结束位置的过去索引(或结束迭代器)。

最后一个总是让人们对循环算法不熟悉，但是当您开始进行数学运算时，它是有意义的。简而言之，将其视为您不 搜索的第一个索引，而不是您 搜索的包含索引。它还使得以迭代或递归方式编写算法代码变得简单明了。

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

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

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;
}

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

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;
}

我们同样可以重载它以只获取一个 vector (我们假设它是排序的)和一个测试值，但为什么要到此为止。我们可以制作一个将模板类型作为参数之一的模板，并且由于 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);
}

然后将使用上一节中的相同测试程序，并产生相同的结果。

---

无递归的二分搜索

一旦掌握了该算法，您很快就会发现它非常适合迭代算法而不是递归算法。老实说，就调用堆栈空间而言，这并不重要。对 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);
}

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